[Silver3] No.09372 상근이의 여행
19 Mar 2022상근이의 여행
문제
상근이는 겨울방학을 맞아 N개국을 여행하면서 자아를 찾기로 마음먹었다.
하지만 상근이는 새로운 비행기를 무서워하기 때문에, 최대한 적은 종류의 비행기를 타고 국가들을 이동하려고 한다.
이번 방학 동안의 비행 스케줄이 주어졌을 때, 상근이가 가장 적은 종류의 비행기를 타고 모든 국가들을 여행할 수 있도록 도와주자.
상근이가 한 국가에서 다른 국가로 이동할 때 다른 국가를 거쳐 가도(심지어 이미 방문한 국가라도) 된다.
풀이
입력부분을 보면 문제에서 사용하고 있는 자료구조를 알려주고 있다. 주어지는 비행 스케줄은 항상 연결 그래프를 이룬다. 바로 해당의 문구로 비행기와 국가의 관계는 그래프 구조를 이루는 것을 알 수 있다. 아직 자료구조에 익숙치 않아, 그래프도 같이 구현하여 소스를 작성해보고자 했다.
해당 문제는 모든 국가가 연결그래프로 연결 되어있어, MST 알고리즘으로 봐도 N개의 국가(정점)은 N-1개의 비행기수(간선)으로 이루어져 있다는걸 알 수 있다.
하지만 BFS와 DFS를 연습하고자 BFS를 이용하여 문제를 해결 하였다.