백준 1976번
-
(백준 1976번 여행 가자 C++) 라이님 블로그 대회 알고리즘 따라잡기 12) Union Find 2PROGRAMMING/알고리즘 2024. 5. 9. 20:07
(노느라) 바쁘다는 핑계로 공부를 소홀히 하는 것 같아 마음이 불편하다.이제는 진짜 매일 1백준 해야겠다!!! 백준 1976번https://www.acmicpc.net/problem/1976 이 문제는 Union Find 라고 해서 봤는데 처음에는 뭔 소리인가 했다. dfs로 풀어야 하나 생각하고 있었는데!Union Find로 아이디어를 틀었다. 이디야에서 샤인히비스커스를 마시면서 깨달은 사실 : 사실 어떤 도시를 몇 번 가는지는 중요하지 않다! 연결된 도시는 무조건 방문이 가능하다. 이 말인 즉, 여행을 가고지 하는 도시들이 하나의 connected graph의 node들이기만 하면 된다는 의미!그리고 하나의 connected graph에 속하는지 아닌지는 root node가 동일한지 아닌지만 확인하..