[Baekjoon] 9372번 : 상근이의 여행 (Python, 최소 신장 트리)

[Baekjoon] 9372번 : 상근이의 여행 (Python, 최소 신장 트리)

 

목차

 

https://www.acmicpc.net/problem/9372

9372번: 상근이의 여행

코드 링크

https://github.com/stellaluminary/Baekjoon

GitHub - stellaluminary/Baekjoon

Python

 

방법 1 - 메모리 30840KB / 시간 292ms / 코드 길이 512B

 

본 문제는 최소 신장 트리에 해당하는 문제로 일반적인 크루스칼 알고리즘과 달리 모든 간선의 cost는 1이다.

따라서 이를 고려한 알고리즘을 구현하면 된다.

 

앞서 cost가 1이라고 말했기 때문에 굳이 edge에 대한 sort과정을 생략하고 cycle인지 아닌지만을 고려한 코드 구현으로 목표를 달성할 수 있다.

 

import sys
input = sys.stdin.readline

def f_p(p, x):
    if p[x] != x:
        p[x] = f_p(p, p[x])
    return p[x]

def union(p, a, b):
    a = f_p(p, a)
    b = f_p(p, b)
    if a < b:
        p[b] = a
    else:
        p[a] = b

t = int(input())
for i in range(t):
    n, m = map(int, input().split())

    p = [j for j in range(n+1)]
    res = 0

    for e in range(m):
        a,b = map(int, input().split())
        if f_p(p, a) != f_p(p, b):
            union(p, a, b)
            res += 1

    print(res)

 

방법 2 - 메모리 30840KB / 시간 180ms / 코드 길이 189B

 

최소 신장 트리 혹은 신장 트리를 알고 있다면 굳이 이를 계산할 필요가 있나 생각이 들 것이다. 왜냐하면 모든 국가는 모든 간선의 cost가 1이고 이에 따라 모든 국가를 연결하는 최소 간선의 수는 결국 "모든 국가의 수-1"이 자명하기 때문이다.

 

이로써 이를 통한 결과를 제출해도 정답이다. 

import sys
input = sys.stdin.readline

t = int(input())
for i in range(t):
    n, m = map(int, input().split())
    for e in range(m):
        a,b = map(int, input().split())
    print(n-1)

 

방법 3 - 메모리 32292KB / 시간 236ms / 코드 길이 459B

 

물론 신장 트리 외 dfs, bfs를 통한 방법 또한 존재한다.

 

간선의 연결에 대하여 쌍방향의 위치를 넣는 graph list를 생성한다.

그리고 해당 graph를 기반으로 각 node를 방문했는지를 판단하는 visit list를 활용한다.

만약 visit에서 특정 index가 방문했다면 1로 설정하고 방문하지 않았다면 dfs로 재귀를 진행한다.

결과적으로 모든 node의 visit이 1로 방문되었다면 count 값을 반환하여 출력한다.

 

import sys
input = sys.stdin.readline

def dfs(idx, cnt):
    visit[idx] = 1
    for i in graph[idx]:
        if visit[i] == 0:
            cnt = dfs(i, cnt+1)
    return cnt

t = int(input())
for _ in range(t):
    n,m = map(int, input().split())
    graph = [[] for _ in range(n+1)]
    for _ in range(m):
        u, v = map(int, input().split())
        graph[u].append(v)
        graph[v].append(u)
    visit = [0]*(n+1)
    cnt = dfs(1, 0)
    print(cnt)