BOJ 1922번: 네트워크 연결

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

1922번: 네트워크 연결

최소 신장트리를 구하는 기본적인 문제이고, 나는 크루스칼 알고리즘을 이용하여 풀었다.

가중치 값을 기준으로 오름차순으로 정렬한 후 간선의 두 정점이 서로 다른 그래프인 경우 해당 간선을 선택해나가는 알고리즘이다.

두 정점이 서로 연결되어있는지 여부를 확인하는 check 함수를 만들어서 사용했고 DFS를 이용하였다.

python으로는 시간초과가 났고, pypy3로 통과했는데 아무래도 check를 DFS말고 다르게 탐색하면 시간을 더 줄일 수 있을 것 같다.

import sys
input = sys.stdin.readline
N = int(input())
M = int(input())
graph = [[] for _ in range(N+1)]
line = []
for _ in range(M):
    line.append(list(map(int, input().split())))
line.sort(key=lambda x:x[2])
ans = 0

def check(a, b):
    st = [a]
    visit = [False]*(N+1)
    visit[a] = True
    while (st):
        v = st.pop()
        if (v==b):
            return False
        for i in graph[v]:
            if (visit[i]==False):
                visit[i] = True
                st.append(i)
    return True

for a, b, c in line:
    if (check(a,b)):
        graph[a].append(b)
        graph[b].append(a)
        ans += c

print(ans)