백준 13418 학교 탐방하기 파이썬 풀이, 반례

난이도 : 골드3

풀이일 : 07086

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

13418번: 학교 탐방하기

---

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

---

풀이 코드

import sys

# 연결 확인 함수
def check(parent, n):
    if parent[n] != n:
        parent[n] = check(parent, parent[n])
    return parent[n]

# 오르막길 더하기 함수
def count(temp):
    parent = [i for i in range(N+1)]
    for j in range(M+1):
        x, y = check(parent, road[j][1]), check(parent, road[j][2])
        # 추가 조건 맞추기
        if x > y:
            x, y = y, x
        if x != y:
            parent[y] = x
            # 오르막길 카운트
            if not road[j][0]:
                temp += 1
    return temp

N, M = map(int, sys.stdin.readline().split())

maxi = mini = 0
road = []

for _ in range(M+1):
    a, b, c = map(int, sys.stdin.readline().split())
    road.append([c, a, b])

# maxi -> 오름차순 순회
road.sort()
maxi = count(maxi) ** 2

# mini -> 내림차순 순회
road.sort(reverse=True)
mini = count(mini) ** 2

print(maxi - mini)

코드 구성

• check : 연결 확인 함수, 이미 연결된 노드라면 연결하지 않음
• count : 오르막길 더하기 함수, check로 확인한 후 연결하는 길이 오르막길인지 카운트
• road : 길의 시작, 끝 점과 오르막/내리막 정보를 저장
• maxi : 최대 피로도 계산을 위해 정렬 후 count 함수 실행
• mini : 최소 피로도 계산을 위해 정렬 후 count 함수 실행

---

반례

입력	3 3 0 1 0 1 2 0 1 3 1 2 3 1
출력	3

---

느낀점

어제 푼 최소 스패닝 트리와 비슷한 유형을 골라서 풀었는데 생각보다 오래걸렸다.

중간에 for 문 조건을 M까지로 써서 틀렸었다. 반례도 잘 안나오지만 반례가 필요도 없었다.