백준 1976 c++ _ 여행가자 _

- 문제 -

 

- 입력 / 출력 -

 

- 예제 입력 -

- 풀이 (1) -

문제를 처음 보자마자 생각한 방법은 그래프를 이용하여 탐색을 진행하면 된다고 생각을 하였다.
처음에는 모든 방문해야하는 도시들을 방문할 때 까지 반복하여 문제를 해결하려고하였다. --- 생각을 잘못함.

결국 다시 문제를 풀었고 처음 방문해야하는 도시를 dfs에 입력으로 넣어주었다.

 

이 두가지를 구현을 하면 쉽게 문제를 해결할 수 있다.

 

1) dfs로 그래프를 탐색 -> 방문한 노드는 방문 처리

2) 방문처리한 위치와 방문해야할 목적지를 비교

- 전체 코드 -

- 풀이 (2) - 

다른 사람의 풀이를 찾다보니 분리 집합 알고리즘을 활용하여서도 이 문제를 더 쉽게 풀수있다는것을 알게되었다.

분리집합 알고리즘에 대해서 처음 들었기에 먼저 알고리즘에 대해서 학습을 하였다.

Union Find = 서로소 집합(Disjoint-Set),분리집합