[백준] 1976.여행 가자 (Swift, Java)

[백준] 1976.여행 가자 (Swift, Java)

https://www.acmicpc.net/problem/1976

1976번: 여행 가자

풀이

1. BFS

입력은 인접행렬로 표현된 그래프가 주어지고, 마지막 줄에는 방문할 노드들이 순서대로 주어집니다.

 

처음에는 단순히 방문한 노드들을 차례대로 2개씩 뽑아서 BFS 를 진행할 생각이었습니다. 최단 경로가 존재한다면 true 를 리턴하고, 존재하지 않는다면 false 를 리턴하는 방식으로 접근하면 된다고 생각했습니다.

 

하지만 m 번만큼 BFS 를 수행해야 한다는 것이 비효율적 이라고 생각되어 다른 방법을 찾기로 하였습니다.

2. DFS

마지막 줄의 노드들은 방문하는 순서로 입력되기 때문에 가장 첫 번째 노드가 시작점이 됩니다.

 

DFS 를 수행하게 되면 같은 그래프 내의 모든 노드를 방문하기 때문에 첫번째 노드에서 DFS 를 시작하면 주어진 그래프에서 어떤 노드들이 첫번째 노드와 연결되어 있는지 알 수 있습니다.

 

마지막 줄에 1 4 라는 입력이 주어졌다고 가정해보겠습니다. 1번 노드와 4번 노드는 서로 인접해있지 않더라도 같은 그래프 내에 있다면 어떻게든 순서대로 방문이 가능합니다.

 

그렇기 때문에 마지막 줄의 입력된 노드들이 모두 같은 그래프 안에 존재한다면 무조건 YES 를 반환하고, 아니라면 NO 를 반환하여 문제를 해결할 수 있습니다.

코드

Swift

Java