문제설명 입출력 예제 개념 이 문제는 모든 국가가 연결되어 있고, 모든 비행기 티켓 가격이 동일하다는 특성 때문에 최소 신장 트리 문제처럼 보일 수 있다. 하지만 여기서 중요한 점은 상근이가 한 국가에서 다른 국가로 이동할 때, 필요에 따라 다른 국가를 거쳐갈 수 있다는 것이다. 이는 실질적으로 모든 비행기를 직접 타고 갈 필요가 없다는 것을 의미한다. 따라서 이 문제의 답은 MST 알고리즘을 사용하지 않고도 간단히 구현할 수 있다. 상근이가 모든 국가를 여행하기 위해서는 전체 국가의 수 - 1 만큼의 비행기를 타면 된다. 왜냐하면 한 국가에서 출발해 모든 다른 국가를 방문하려면, 국가의 수보다 비행기를 하나 적게 타면 되기 때문이다. 풀이 #include using namespace std; int m..
