https://school.programmers.co.kr/learn/courses/30/lessons/150366

---

1. 코드

def toInt(x, y):
    return int(x), int(y)

def solution(commands):
    def replace(old, new):
        for i in range(1, length):
            for j in range(1, length):
                if graph[i][j] == old:
                    graph[i][j] = new

    def update(R, C, new):
        target = link[R][C]
        for i in range(1, length):
            for j in range(1, length):
                if link[i][j] == target:
                    graph[i][j] = new

    def merge(r1, c1, r2, c2):
        main = (None, None)
        sub = (None, None)
        if 'EMPTY' == graph[r1][c1] and graph[r2][c2]:
            main = (r2, c2)
            sub = (r1, c1)
        elif graph[r1][c1] and 'EMPTY' == graph[r2][c2]:
            main = (r1, c1)
            sub = (r2, c2)
        elif graph[r1][c1] and graph[r2][c2]:
            main = (r1, c1)
            sub = (r2, c2)

        old = link[sub[0]][sub[1]]
        new = link[main[0]][main[1]]
        for i in range(1, length):
            for j in range(1, length):
                if link[i][j] == old:
                    link[i][j] = new
                    graph[i][j] = graph[main[0]][main[1]]

    def unmerge(r, c):
        old = graph[r][c]
        target = link[r][c]
        for i in range(1, length):
            for j in range(1, length):
                if link[i][j] == target:
                    link[i][j] = (i, j)
                    graph[i][j] = 'EMPTY'
        graph[r][c] = old


    length = 51
    answer = []
    graph = [['EMPTY'] * length for _ in range(length)]
    link = [[False, False] * length for _ in range(length)]
    for i in range(1, length):
        for j in range(1, length):
            link[i][j] = (i, j)


    for line in commands:
        l = line.split(' ')
        if l[0] == 'UPDATE':
            if len(l) == 4:
                R, C = toInt(l[1], l[2])
                update(R, C, l[3])
            else:
                replace(l[1], l[2])
        elif l[0] == 'MERGE':
            R1, C1 = toInt(l[1], l[2])
            R2, C2 = toInt(l[3], l[4])
            if (R1, C1) == (R2, C2):
                continue
            merge(R1, C1, R2, C2)
        elif l[0] == 'UNMERGE':
            R, C = toInt(l[1], l[2])
            unmerge(R, C)
        else:
            R, C = toInt(l[1], l[2])
            answer.append(graph[R][C])

    return answer

---

2. 후기

처음 풀이는 병합되지 않은 (i,j) 의 상태를 False 상태로 저장하는 풀이었는데 테스트 케이스에서 절반정도가 틀렸다.

도저히 문제를 못찾겠어서 병합 상태를 나타내는 link[i][j] 값을 기본적으로 False가 아닌 (i,j) 를 가지도록 수정해봤는데 풀렸다.

(i,j) 좌표에 UNMERGE가 발생하여 병합이 제거된다면 link[i][j]는 초기값인 (i,j) 를 가진다.