[백준] Python - 여행 가자

메모/알고리즘

Floodnut 2022. 3. 25. 15:15

1976번: 여행 가자

동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인

www.acmicpc.net

Union-Find를 쓸 수 있는 기본적인 분리 집합 문제이다.

여행을 가려는 사람은 왔던 도시를 다시 거칠 수 있고 입력의 마지막으로 주어진 모든 도시를 갈 수만 있으면 된다.

기본적인 Union-Find를 사용하여 부모 노드를 연결하고 같은 부모를 가진 집합이라면 서로 연결되었다고 볼 수 있다.

GitHub - Floodnut/algorithm: 알고리즘 풀이 모음

알고리즘 풀이 모음. Contribute to Floodnut/algorithm development by creating an account on GitHub.

github.com