[백준] 1976번, 여행 가자 (JavaScript)

Algorithm

📌 문제 정보 : 여행 가자

• 문제 분류 : 자료 구조, 그래프 이론, 그래프 탐색, 분리 집합
• 문제 출처 : 백준 골드 4, 여행가자

✅ 접근 과정

문제는 도시와 이 도시들 간의 연결 정보가 주어졌을 때, 마지막에 주어진 여행 경로에 있는 도시들을 한 번에 모두 방문할 수 있는지 확인하는 것이었다.

조금 생각해보니 한 번 방문했던 도시를 여러번 방문해도 상관 없다면 유니온 파인드를 이용하여 여행 경로의 도시들이 모두 동일한 루트를 가지고 있다면 여행 경로를 모두 방문할 수 있다는 아이디어가 떠올랐다.

주어진 정보를 통해 각 도시(정점)들에 대한 유니온 파인드 배열을 만들고 확인 방식으로 접근했다.

유용했던 정보 : 없음

✨ 풀이 코드

🚩 마치며

유니온 파인드를 사용한다면 어렵지 않은 문제였지만 유니온 파인드 배열이 루트로 초기화되어 있지 않은 경우가 존재하여 이 부분을 발견하고 해결하는데 생각보다 시간이 걸렸다. 좀 더 이런 유형의 문제를 풀어보면서 실수를 줄여나가야 겠다.