신장트리(백준 알고리즘 9372번)

♣ 신장트리

연결 그래프의 부분 그래프로서, 그래프의 모든 노드 간선의 부분 집합으로 구성되는 트리

모든 노드는 적어도 하나의 간선에 연결되어 있다.

 

 

n개의 노드(정점)을 가지는 그래프가 있다면, n개의 정점을 모두 연결할 수 있는 n-1 개의 엣지(간선)으로 이뤄진 부분 그래프들을 신장트리라고 한다. 즉 최소의 간선 수는 n-1이다. 

 

 

 

 

♣ 참고 자료

https://limecoding.tistory.com/123

신장 트리(Spanning Tree)

 

 

♣ 백준 알고리즘 9372번 이해

 

 

 

우선 문제를 잘 이해해야 한다. 모든 나라를 방문하기 위해 '나라와 나라 사이를 건너는 횟수'가 아니라 '타는 비행기의 종류' 최솟값을 구하는 것이다. 

 

한 나라와 다른 나라 사이를 왕복하는 비행기를 한 종류로 친다. 따라서 몇 개 종류의 비행기가 주어지는가에 상관없이 모든 나라를 방문해야 하므로 모든 나라가 연결되어 있어야 한다. 즉 나라를 노드(정점)으로 치면 노드를 모두 연결할 수 있는신장트리가 되어야 한다는 말이다. 

 

예를 들어 나라의 수가 4개, 비행기 종류가 6개라고 해보자. 

1 2

1 3

4 2

3 2

3 4

4 1

 

이를 그래프로 나타내면 아래와 같다(노드 4개, 간선 6개)

그런데 여기서 최소한의 종류의 비행기를 타고 나라들을 방문하면 되니까 굳이 안 타도 되는 노선(비행기의 종류)을 없애보도록 하자.

 

6개의 노선 중 3개는 없애버려도 여전히 모든 국가에 방문할 수 있다. 이 형태가 바로 신장트리이다. 그리고 신장트리에서 필요한 최소 간선의 수는 항상 (노드의 수 -1) 이다. 

 

따라서 위 문제에서 n개의 나라가 노드로 주어질 때, 어차피 모든 노드에 방문할 수 있도록 간선이 구성되어 있을 것이므로 최소의 간선 수를 구하려면 n-1을 구하면 된다. 

 

 

♣ 코드 제출

 

신장트리인 것만 알면 주어진 비행기 종류가 몇 개인지 아예 몰라도 되는 문제였다. 아예 감을 못 잡고 있었는데 신장트리라는 개념을 알게 되니 엄청 쉬운 문제였다. 이 문제가 트리 알고리즘 문제들 중에서 가장 낮은 단계의 문제인 것 같다.