백준 9372번: 상근이의 여행 (JAVA) <BFS>

 

문제 해석

 

테스트 케이스 T가 주어진다.

테스트 케이스 실행시 처음에 국가의 수 N과 비행기 종류 M이 주어진다.

비행기 종류 M만큼 각 비행기가 운행하는 국가들이 주어진다. ex) 1 2가 주어질시 1국가와 2국가 운행(왕복)

모든 국가를 여행해야하고 타는 비행기 종류를 최소한으로 해야한다.

 

알고리즘

 

사실 이 문제는 풀 의미가 없었다.

모든 국가를 무조건 여행해야 하는 상태에서 비행기 종류 하나당 운행편이 한개뿐이고 

같은 경로를 가진 두 개의 비행기가 있더라도 비행기 종류를 최소화해야 하고

경유해서 가는 경우를 허용하면서

비행기 타는 횟수는 고려하지 않기에

정답은 어떤 입력이 들어오든 무조건 N-1이다.

하지만 원래 BFS로 푸는 문제이고 BFS 연습을 하고자 인접행렬을 이용하여 노드 간 관계를 나타내고 탐색하였다.

 

BFS

 

BFS는 현재 검색 노드와 가까운 관계에 있는 노드부터 탐색하기 때문에 두 노드 사이의 경로를 탐색할 때 활용하기 좋다.

 

코드

 

 

예시를 하나 실행해보면

1 2 3 세개의 여행지가 있고 

비행기 종류 당 운항이 (1, 2) / (1, 3) / (2, 3) 으로 주어지는 경우

인접행렬에서 데이터 1을 가지는 것만 살펴보면

[1, 2] / [1, 3] / [2, 1] / [2, 3] / [3, 1] / [3, 2] 이다.

 

 

함수 실행 시 1차 while문 수행으로 cnt는 2가 되고 queue에는 2와 3이 들어있게 된다.

하지만 모든 여행지에 대하여 방문기록이 남아있기 때문에 두번의 poll을 진행하고 while문을 탈출하게 된다.

현실에서는 1 -> 2 -> 1 -> 3 이 1 -> 2 -> 3 여행 경로보다 비효율적이지만

이 문제에서는 타는 비행기 종류 개수만 따지므로 고려하지 않아도 되는 것 같다.