title: "[프로그래머스] 표 병합 Python 파이썬 해설 (Level 3) - 이도훈"
cleanUrl: "programmers/150366"
description: "프로그래머스 Level 3 문제 [표 병합]의 풀이를 정리합니다."
from collections import defaultdict
# Union-find로 풀어보자.
# 문제가 작아서 경로 압축은 필요 없을듯?
p, val = {}, {}
for r in range(1, 51):
for c in range(1, 51):
p[(r, c)] = (r, c)
def find(x):
# x가 루트 노드이면 x가 대표입니다.
if x == p[x]:
return x
# 그렇지 않다면, 재귀적으로 find를 호출하여 루트 노드를 찾습니다.
p[x] = find(p[x])
return p[x]
def update_cell(x, v):
# x가 속한 cell 값을 업데이트합니다.
val[find(x)] = v
def update_all(vold, vnew):
for x, v in val.items():
if v == vold:
val[x] = vnew
def merge(x, y):
x, y = find(x), find(y)
# 이미 x와 y가 같은 셀일경우 무시합니다.
if x == y:
return
# 그렇지 않다면, x에 y를 포함시킵니다.
p[y] = x
# x에 값이 할당되어 있고, y에 값이 할당되어 있었다면 지웁니다.
# y에만 값이 할당되어 있으면 x의 값을 그것으로 업데이트합니다.
if y in val:
if x in val:
val.pop(y)
else:
val[x] = val[y]
val.pop(y)
def unmerge_cell(x, child):
# x가 리프 노드이면 가리키던 부모 노드만 삭제합니다.
if x not in child:
p[x] = x
return
# 리프 노드가 아니면 자식 노드에 대해 unmerge_cell을
# 재귀적으로 수행 후 부모 노드를 삭제합니다.
for ch in child[x]:
unmerge_cell(ch, child)
p[x] = x
def unmerge(x):
# parent 관계로부터 child 관계를 업데이트 해둡니다.
child = defaultdict(list)
for ch, pa in p.items():
if ch != pa:
child[pa].append(ch)
# x가 속한 cell의 루트를 찾고, cell의 값을 기억해둡니다.
root = find(x)
v = val.pop(root) if root in val else None
# 루트로부터 재귀적으로 unmerge 합니다.
unmerge_cell(root, child)
# 초기화 과정에서 값이 삭제되었으므로,
# x에 값을 다시 할당합니다.
if v:
val[x] = v
def solution(commands):
answer = []
for command in commands:
tokens = command.split()
# UPDATE r c value
if len(tokens) == 4 and tokens[0] == 'UPDATE':
r, c = map(int, tokens[1:3])
v = tokens[-1]
x = (r, c)
update_cell(x, v)
# UPDATE value1 value2
elif len(tokens) == 3 and tokens[0] == 'UPDATE':
vold, vnew = tokens[1:]
update_all(vold, vnew)
# MERGE r1 c1 r2 c2
elif tokens[0] == 'MERGE':
r1, c1, r2, c2 = map(int, tokens[1:])
x, y = (r1, c1), (r2, c2)
merge(x, y)
# UNMERGE r c
elif tokens[0] == 'UNMERGE':
x = tuple(map(int, tokens[1:]))
unmerge(x)
# PRINT r c
else:
x = tuple(map(int, tokens[1:]))
answer.append(val.get(find(x), 'EMPTY'))
return answer
프로그래머스 코딩테스트 연습 https://school.programmers.co.kr/learn/challenges