백준 1197 최소 스패닝 트리 파이썬 풀이

난이도 : 골드4

풀이일 : 07075

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

1197번: 최소 스패닝 트리

---

링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐

---

1차 시도 오답 -> 3% 틀렸습니다 

import sys

def check(num):
    if parent[num] != num:
        parent[num] = check(parent[num])
    return parent[num]

V, E = map(int, sys.stdin.readline().split())

parent = [i for i in range(V+1)]
queue = []
result = 0

for i in range(E):
    a, b, c = map(int, sys.stdin.readline().split())
    queue.append([c, a, b])

queue.sort()

for i in range(len(queue)):
    x, y = queue[i][1], queue[i][2]
    if x < y:
        x, y = y, x
    if check(x) != check(y):
        parent[x] = y
        result += queue[i][0]

print(result)

코드 구성

• check 함수 : 파라미터로 들어온 노드의 루트를 찾아 반환
• parent : 부모 정보를 기록, 최초 설정은 자기 자신으로 설정
• queue : 가중치, 연결 노드 순서로 주어진 정보 삽입 및 정렬

틀린 이유

• 마지막 조건문에서 x, y로 parent 수정

---

최종 정답

import sys

# 루트 찾기 함수
def check(num):
    if parent[num] != num:
        parent[num] = check(parent[num])
    return parent[num]

V, E = map(int, sys.stdin.readline().split())

parent = [i for i in range(V+1)]
queue = []
result = 0

# 가중치 기준으로 연결 정보 정렬
for _ in range(E):
    a, b, c = map(int, sys.stdin.readline().split())
    queue.append([c, a, b])

queue.sort()

for i in range(len(queue)):
    x, y = queue[i][1], queue[i][2]
    # 연결 조건 통일
    if x < y:
        x, y = y, x
    # 루트 노드가 다를 때 연결
    if check(x) != check(y):
        parent[check(y)] = check(x)
        result += queue[i][0]

print(result)

코드 변화

• 마지막 조건문에서 x, y가 아니라 두 가지를 check 함수에 넣은 반환값을 parent에 저장

---

느낀점

로직은 금방 생각해냈는데, 생각보다 오래 걸렸다.

중간에 왜 안되는지 이해가 안되어서 시간을 많이 잡아먹었는데, 틀린 부분을 오늘 안에 발견해서 다행일 지경