그래프
-
알고리즘) 프로그래머스 Graph, 사이클 제거알고리즘/프로그래머스 고득점 Kit 2020. 5. 1. 15:37
프로그래머스 고득점Kit - Graph 사이클 제거 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 노드의 사이즈를 돌면서 하나씩 제거하고 사이클이 있는지 없는지 체크했다. 결과적으로 정확성 테스트는 다 맞지만, Cycle을 확인하는 메소드를 재귀로 호출하여 효율성은 다 틀린 것 같다. 이후 이 문제를 푼 분들의 로직을 보면서 가장 매력적인 로직을 찾아냈다. 전체 노드의 갯수 -1 개가 되면 사이클이 없다는 것이다. 다만, 컴포넌트의 갯수가 1개가 아닌 2개~n개일 때는 컴포넌트의 갯수도 같이 세줘야 한다는 것이다. 이 로직에 따라 코드를 짜봤지만, ..
-
알고리즘) 프로그래머스 Graph, 순위알고리즘/프로그래머스 고득점 Kit 2020. 4. 27. 16:14
프로그래머스 고득점 Kit - Graph 순위 풀이 (2020.04.27) 문제의 조건에서 경기 결과에 모순이 없으며, A>B, B>C 이면 항상 A>B>C의 순서가 매겨진다고 되어있다. 따라서, 경기 결과가 유실되어도 특정 선수(A)가 이긴 상대들은 A를 이긴 상대들이 이길 수 있다는 뜻이다. 경기 결과 입력 후, 서로 상관관계에 따라 입력을 해주고 랭킹을 부여할 수 있는 선수들을 찾아 return했다. 1. 전체 경기 결과를 이긴 상대 리스트, 진 상대 리스트에 담아준다. (선수 Index에 맞춰서) 2. 서로 경기 결과에 대해 이기고 진 상대들을 업데이트 해준다. 3. 경기 결과가 모두 있는 선수들은 Rank를 부여할 수 있으므로, 전체 경기 결과가 있는 선수들의 수를 return해준다. (2020..
-
알고리즘) 프로그래머스 Graph, 가장 먼 노드알고리즘/프로그래머스 고득점 Kit 2020. 4. 25. 15:50
프로그래머스 고득점 Kit - Graph 가장 먼 노드 풀이 2020.04.25) 그래프를 이용해 푸는 문제다. 이에 LinkedList와 PriorityQueue(우선순위 큐)를 이용해 BFS로 문제를 풀었다. 마지막 depth의 노드 수를 구하는 것이기 때문에 BFS가 적절하다고 생각됐다. 1. 루트인 1부터 시작해서 연결된 노드를 탐색한다. 2. 우선순위 큐에 depth를 기준으로 정렬해서 BFS 탐색을 할 수 있도록한다. 이때, visit을 남겨서 depth를 설정할 수 있게 도왔다. 3. depth별로 노드의 수를 세면서, depth가 깊어질 때마다 노드의 수를 0으로 초기화 시켜줬다. 4. 마지막 depth에서 while문을 탈출하면서 노드의 수를 센 result가 return될 수 있게 설정..