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