kipo3195   1년 전

유니온 파인드 문제 유형으로 접근했는데.. 아직 유니온 파인드 개념에 대한 이해가 부족해서 도저히 어떻게 설계해야할지 모르겠더군요

그래서 서로 갈 수 있는 인접리스트 정보가 주어지니 인접리스트를 생성하고 DFS 탐색으로 각 도시 별로 거쳐 갈 수 있는 모든 경우의 수를 구하고 SET에 넣은다음, 가야할 경로가 여행경로 A -> B -> C -> D라면 A에서 갈 수 있는 경로 중에 B가 있는지, B에서 갈 수 있는 경로중에 C가 있는지를 찾는 방법으로 풀이했습니다. 다만, 문제에 트릭? 이라면 트릭인데 동일한 도시를 한번 더 가는 케이스를 생각하지 못해서 반례를 찾아 풀이했습니다.

댓글을 작성하려면 로그인해야 합니다.