9372 상근이의 여행

백준 문제를 풀면서 내용 정리가 필요할것 같아서 블로그에 새로 만들었습니다.

대학교에서 자료구조 과목을 배우면서 기초적인 내용은 습득했다고 생각했는데, 역시 몇달도 지나지 않아서 다 까먹고 안배운 내용도 많다는것을 알게 되었습니다.

9372번 문제를 보고 이것 저것 생각하다가 의문점이 2가지 생겼습니다.

1. 어디에서 시작하는지?
2. 만약 연결되지 않는 국가가 있는 경우가 존재하는가?

1번은 문제에 오류가 있을 가능성도 있지만, 오류가 있을 가능성은 낮기 때문에 아마 어디서 시작하던 상관이 없다는 의미로 생각했습니다. 2번은 “입력” 부분에 나와있는 연결 그래프에서 답을 찾을 수 있었습니다.

연결 그래프는 그래프 내부의 임의의 서로 다른 두 꼭짓점이 연결된 그래프라고 나와있습니다. 즉 문제에서는 모든 국가끼리 각각 어떤 비행 스케쥴로든 연결이 되어있다는 의미로 해석할 수 있습니다.

따라서 BFS와 같이 1번 국가를 기점으로 연결된 모든 노드를 조사해서 연결된 노드 1개당 새로운 종류의 비행 스케쥴이 있음으로 1를 추가해주면 되겠지 싶었습니다.

그런데 이 문제가 포함된 분류가 “최소 신장 트리”여서 관련된 내용으로 풀어야 되나 싶어서 관련 내용을 찾아보게 되었습니다.

신장 트리(spanning tree)는 순환이 없는(본문의 no cycles) 연결 그래프로 정의 되어있고, 최소 신장 트리 (minimum spanning tree)는 신장 트리중 간선(연결된 선)의 가중치 합이 최소(the minimum possible total edge weight)가 되는 경우를 말합니다. (줄여서 MST라 부르는것 같습니다.)

즉 이 문제가 최소 신장 트리에 포함된 이유는 주어진 국가와 비행 스케쥴로 최소 신장 트리를 만들어 간선의 개수를 출력하는 문제로 볼 수 있습니다.

그런데 MST에서는 n개의 꼭짓점이 있을때, 간선의 수는 n-1개라고 적혀있습니다. (If there are n vertices in the graph, then each spanning tree has n − 1 edges.)

궁금해서 백준 질문 개시판에 들어가서 찾아보니 이미 다들 생각하신 내용이더군요 실제 solution

저는 이 과정까지 한참 걸렸는데 역시 ICPC 대회는 무섭군요…