728x90
난이도 : 골드3
풀이일 : 07086
https://www.acmicpc.net/problem/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까지로 써서 틀렸었다. 반례도 잘 안나오지만 반례가 필요도 없었다.
'알고리즘 > 🥇 골드' 카테고리의 다른 글
백준 1111 IQ Test 파이썬 풀이 (0) | 2023.07.21 |
---|---|
백준 4386 별자리 만들기 파이썬 풀이 (0) | 2023.07.10 |
백준 1197 최소 스패닝 트리 파이썬 풀이 (0) | 2023.07.07 |
백준 2146 다리 만들기 파이썬 풀이 (0) | 2023.07.05 |
백준 2638 치즈 파이썬 풀이 반례 (0) | 2023.05.15 |