표 병합

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