[백준_python] 상근이의 여행 || 9372 (최소 신장 트리)

www.acmicpc.net/problem/9372

9372번: 상근이의 여행

위 예제 입력을 보고 그래프를 따라 그려보면, 모든 정점들이 이어져 있다.

 

신장 트리(spanning tree)

가장 적은 간선을 가진 그래프이다.

n개의 정점을 가지는 그래프의 최소 간선의 개수는 n-1개이고, 이러한 트리 형태를 뜻한다.

 

- 하나의 그래프 속에는 많은 신장 트리가 존재할 수 있다.(DFS와 BFS를 이용하여 찾을 수 있다)- 모든 정점들이 연결되어 있어야 하며, 사이클은 포함해서는 안된다.

 

최소 신장 트리(Minimum Spanning Tree)

신장 트리에서 사용된 간선들의 가중치 합이 최소인 트리를 말한다.
간선의 가중치를 고려하여 최소 비용을 선택하는 것.
마찬가지로, n개의 정점과 n-1개의 간선을 사용하며, 사이클이 포함되서는 안된다.

---

sys로 입력을 받지 않으면, 시간 초과가 발생하기 때문에 꼭 sys를 통해 입력을 받아주어야 했다.

# 상근이의 여행
import sys


def BFS(start):
    queue = [start]
    cnt = 0
    while queue:
        start = queue.pop(0)
        for i in range(1, n+1):
            if not visited[i] and plane[start][i] == 1:
                queue.append(i)
                visited[i] = True
                cnt += 1
    return cnt  # 정점을 이동할 때마다 개수를 세어줌


t = int(sys.stdin.readline())  # 테스트 케이스의 수
for _ in range(t):
    # n : 국가(정점)의 수, m : 비행기(간선)의 종류
    n, m = map(int, sys.stdin.readline().split(' '))
    plane = [[0]*(n+1) for _ in range(n+1)]
    visited = [False] * (n+1)

    for _ in range(m):
        a, b = map(int, sys.stdin.readline().split(' '))
        plane[a][b] = plane[b][a] = 1  # 두 국가를 왕복하는 비행기 표시(그래프)

    print(BFS(1)-1)  # 모든 정점을 방문하는 최소 개수는 1을 빼주어야 한다.

처음에는 간선의 최소 개수를 출력해야 하기 때문에, 최단 거리를 구하는 것인듯 하여 BFS를 이용하고자 했다.
그렇지만 이렇게 1을 빼주는 것에서 정점의 개수에서 1을 빼주는 것과 다를 바가 없다는 것을 알게 되었다.

---

#상근이의 여행

import sys
t = int(sys.stdin.readline())
for i in range(t):
    n, m = map(int, sys.stdin.readline().split())
    for j in range(m):
        a, b = map(int, sys.stdin.readline().split())
    print(n - 1)

 

좀 더 간단하게 표현이 가능했다.
 
최소 신장 트리, 신장 트리에 대한 개념을 완전히 잊고 있었다...ㅎㅎㅎ;