목록Union-FInd (1)
Optimal Solution
[백준, C++] 1976 - 여행 가자
https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 문제 분석 그래프가 있고, 이 그래프에서 방문하고자 하는 정점의 번호가 주어진다. 이 때, 이 정점들을 모두 경유할 수 있는 경로가 있는지 탐색하면 된다. 사실 문제를 보고 이 문제는 BFS로도 충분히 풀 수 있을 것 같다는 생각이 들었지만, disjoint-set, 즉 Union-Find를 활용해 풀 수 있을 것이라는 생각이 들었다. 그래서 Union-Find로 한 번 풀고, BFS로 한 번 더..
알고리즘
2023. 9. 24. 22:24