[SWEA][Python3] 1849. 영준이의 무게측정
2019. 5. 16. 01:45 |
프로그래밍/삼성 SWEA
나의 풀이 :
from collections import defaultdict
def find(a):
if not parent[a]:
return a
pa = parent[a]
parent[a] = find(pa)
weight[a] += weight[pa]
return parent[a]
def union(a, b, w):
pa = find(a)
pb = find(b)
if pa == pb:
return
diff = weight[b] - weight[a]
if rank[pa] > rank[pb]:
pa, pb = pb, pa
w = -w
diff = -diff
weight[pa] = w + diff
parent[pa] = pb
if rank[pa] == rank[pb]:
rank[pb] += 1
T = int(input())
for tc in range(1, T + 1):
N, M = map(int, input().split())
parent = defaultdict(int)
weight = defaultdict(int)
rank = defaultdict(int)
ans = []
for _ in range(M):
work = input()
if work[0] == '!':
a, b, w = map(int, work.split()[1:])
union(a, b, w)
else:
a, b = map(int, work.split()[1:])
if find(a) == find(b):
ans.append(weight[a] - weight[b])
else:
ans.append('UNKNOWN')
print('#{} {}'.format(tc, ' '.join(map(str, ans))))
한마디 :
이번 기회에 Union-Find를 확실히 익혀야겠다.
'프로그래밍 > 삼성 SWEA' 카테고리의 다른 글
| [SWEA][Python3] 1259. [S/W 문제해결 응용] 7일차 - 금속막대 (0) | 2019.05.29 |
|---|---|
| [SWEA][Python3] 1265. [S/W 문제해결 응용] 9일차 - 달란트2 (0) | 2019.05.29 |
| [SWEA][Python3] 4112. 이상한 피라미드 탐험 (0) | 2019.05.27 |
| [SWEA][Python3] 1798. 범준이의 제주도 여행 계획 (0) | 2019.05.23 |
| [SWEA][Python3] 1248. [S/W 문제해결 응용] 3일차 - 공통조상 (0) | 2019.05.18 |
| [SWEA][Python3] 1245. [S/W 문제해결 응용] 2일차 - 균형점 (1) | 2019.05.17 |
| [SWEA][Python3] 1247. [S/W 문제해결 응용] 3일차 - 최적 경로 (0) | 2019.05.09 |
| [SWEA][Python3] 5357. 터널 속의 기차 (0) | 2019.05.02 |
최근에 달린 댓글 최근에 달린 댓글