문제

programmers.co.kr/learn/courses/30/lessons/150366

당신은 표 편집 프로그램을 작성하고 있습니다.
표의 크기는 50 × 50으로 고정되어있고 초기에 모든 셀은 비어 있습니다.
각 셀은 문자열 값을 가질 수 있고, 다른 셀과 병합될 수 있습니다.

위에서 r번째, 왼쪽에서 c번째 위치를 (r, c)라고 표현할 때, 당신은 다음 명령어들에 대한 기능을 구현하려고 합니다.

"UPDATE r c value"
(r, c) 위치의 셀을 선택합니다.
선택한 셀의 값을 value로 바꿉니다.

"UPDATE value1 value2"
value1을 값으로 가지고 있는 모든 셀을 선택합니다.
선택한 셀의 값을 value2로 바꿉니다.

"MERGE r1 c1 r2 c2"
(r1, c1) 위치의 셀과 (r2, c2) 위치의 셀을 선택하여 병합합니다.
선택한 두 위치의 셀이 같은 셀일 경우 무시합니다.
선택한 두 셀은 서로 인접하지 않을 수도 있습니다. 이 경우 (r1, c1) 위치의 셀과 (r2, c2) 위치의 셀만 영향을 받으며, 그 사이에 위치한 셀들은 영향을 받지 않습니다.
두 셀 중 한 셀이 값을 가지고 있을 경우 병합된 셀은 그 값을 가지게 됩니다.
두 셀 모두 값을 가지고 있을 경우 병합된 셀은 (r1, c1) 위치의 셀 값을 가지게 됩니다.
이후 (r1, c1) 와 (r2, c2) 중 어느 위치를 선택하여도 병합된 셀로 접근합니다.

"UNMERGE r c"
(r, c) 위치의 셀을 선택하여 해당 셀의 모든 병합을 해제합니다.
선택한 셀이 포함하고 있던 모든 셀은 프로그램 실행 초기의 상태로 돌아갑니다.
병합을 해제하기 전 셀이 값을 가지고 있었을 경우 (r, c) 위치의 셀이 그 값을 가지게 됩니다.

"PRINT r c"
(r, c) 위치의 셀을 선택하여 셀의 값을 출력합니다.
선택한 셀이 비어있을 경우 "EMPTY"를 출력합니다.

실행할 명령어들이 담긴 1차원 문자열 배열 commands가 매개변수로 주어집니다. commands의 명령어들을 순서대로 실행하였을 때, "PRINT r c" 명령어에 대한 실행결과를 순서대로 1차원 문자열 배열에 담아 return 하도록 solution 함수를 완성해주세요.

풀이

유니온 파인드

parent 배열에는 자신의 부모 노드를 저장하고 graph에는 셀의 value를 저장합니다.

UPDATE r c value

find(x, y) 메서드를 활용해 부모 노드를 찾은 후, 부모 노드의 값을 변경합니다.

UPDATE value1 value2

50x50의 표에서 부모 노드의 value 값이 value1인 노드의 값을 모두 value2로 변경합니다.

MERGE r1 c1 r2 c2

union(Point1, Point2) 메서드를 통해 문제의 조건에 맞게 병합합니다.

UNMERGE r c

문제의 핵심입니다.
(r, c)의 부모 노드(pr, pc)와 셀 value(prev_s) 값을 구합니다. 병합을 해제하기 위해 50x50 표에서 부모가 (r, c)와 같은 점을 모두 구하여 임시 배열에 저장합니다. 임시 배열의 모든 점을 부모를 자신으로, 셀은 EMPTY 값으로 초기화합니다. 마지막으로 점 (r, c)의 부모를 자신으로, 이전에 구한 셀 값(prev_s)으로 지정합니다.

PRINT r c

해당하는 지점의 부모 노드 value 값을 answer 배열에 추가합니다.

코드

import sys
sys.setrecursionlimit(10**8)

MAX = 51
parent = [[[i, j] for j in range(MAX)] for i in range(MAX)]
graph = [['EMPTY' for _ in range(MAX)] for _ in range(MAX)]

def find(x, y):
    if parent[x][y] == [x, y]:
        return parent[x][y]
    parent[x][y] = find(parent[x][y][0], parent[x][y][1])
    return parent[x][y]


def union(a, b, c, d):

    a, b = find(a, b)
    c, d = find(c, d)

    if a == c and b == d:
        return

    if graph[a][b] == 'EMPTY':
        parent[a][b] = [c, d]
    else:
        parent[c][d] = [a, b]

def solution(commands):
    answer = []
    for command in commands:
        li_command = command.split()
        if li_command[0] == 'UPDATE' and len(li_command) == 4:
            px, py = find(int(li_command[1]), int(li_command[2]))
            graph[px][py] = li_command[3]

        elif li_command[0] == 'UPDATE':
            for i in range(MAX):
                for j in range(MAX):
                    px, py = find(i, j)
                    if graph[px][py] == li_command[1]:
                        graph[px][py] = li_command[2]

        elif li_command[0] == 'MERGE':
            union(int(li_command[1]), int(li_command[2]), int(li_command[3]), int(li_command[4]))

        elif li_command[0] == 'UNMERGE':
            px, py = find(int(li_command[1]), int(li_command[2]))
            prev_s = graph[px][py]
            temp_li = []
            for i in range(MAX):
                for j in range(MAX):
                    if i == int(li_command[1]) and j == int(li_command[2]):
                        continue
                    if [px, py] == find(i, j):
                        temp_li.append([i, j])
            for x, y in temp_li:
                parent[x][y] = [x, y]
                graph[x][y] = 'EMPTY'

            parent[int(li_command[1])][int(li_command[2])] = [int(li_command[1]), int(li_command[2])]
            graph[int(li_command[1])][int(li_command[2])] = prev_s

        elif li_command[0] == 'PRINT':
            px, py = find(int(li_command[1]), int(li_command[2]))
            answer.append(graph[px][py])

    return answer