[프로그래머스][Python] 2023 KAKAO BLIND RECRUITMENT : 표병합

📚 문제

---

Lv 3

• MERGE 와 UNMERGE 가 핵심이며 이를 위해 DSU 알고리즘을 사용했다.
  • DSU 알고리즘은 Union Find 이다.
• 2차원 배열을 1차원으로 변환하여 Union 시킨다.
• DSU 알고리즘에서는 Find 후에 가장 Parent Node 를 사용해서 다른 Node 들을 Union 해야한다.

💡 풀이과정

---

1. re 를 사용하여 커맨드를 분리한다.
2. MERGE 시 Union 한다.
3. UNMERGE 시 해당 값으로 Union 된 모든 노드들을 초기화한다.

💻 코드

---

import re


class DSU:
    def __init__(self):
        self.par = [n for n in range(2501)]

    def find(self, x):
        if self.par[x] != x:
            self.par[x] = self.find(self.par[x])
        return self.par[x]

    def union(self, x, y, matrix):
        xr, yr = self.find(x), self.find(y)
        x_x, x_y = xr // 50, (xr-1) % 50
        if xr == yr:
            return False
        elif matrix[x_x][x_y]:
            self.par[yr] = xr
        else:
            self.par[xr] = yr
        return True

    def deunion(self, x, matrix):
        xr = self.find(x)
        value = matrix[xr//50][(xr - 1)%50]
        change_list = []
        for index, p in enumerate(self.par):
            if self.find(p) == xr:
                change_list.append(index)
                matrix[index//50][(index - 1)%50] = ""
        for c in change_list:
            self.par[c] = c
        matrix[x//50][(x-1)%50] = value


def solution(commands):
    answer = []

    matrix = [['' for _ in range(51)] for _ in range(51)]
    dsu = DSU()

    pattern = re.compile(r'(UPDATE|MERGE|UNMERGE|PRINT) (\S+) (\S+) ?(\S*) ?(\S*)')
    for com in commands:
        command = re.findall(pattern, com)[0]

        if command[0] == 'UPDATE':
            if command[3]:
                r, c, value = command[1:4]
                r = int(r)
                c = int(c)
                p = dsu.find((r-1)*50 + c)
                matrix[p//50][(p-1)%50] = value
            else:
                value1, value2 = command[1:3]
                if value1 == value2:
                    continue
                for i in range(50):
                    for j in range(50):
                        if matrix[i][j] == value1:
                            matrix[i][j] = value2
        elif command[0] == 'MERGE':
            r1, c1, r2, c2 = command[1:]
            r1 = int(r1)
            c1 = int(c1)
            r2 = int(r2)
            c2 = int(c2)

            dsu.union((r1 - 1) * 50 + c1, (r2 - 1) * 50 + c2, matrix)
        elif command[0] == 'UNMERGE':
            r, c = command[1:3]
            r = int(r)
            c = int(c)

            dsu.deunion( (r - 1) * 50 + c, matrix)
        elif command[0] == 'PRINT':
            r, c = command[1:3]
            r = int(r)
            c = int(c)
            p = dsu.find((r-1) * 50 + c)
            if matrix[p//50][(p-1)%50] != '':
                answer.append(matrix[p//50][(p-1)%50])
            else:
                answer.append("EMPTY")

    return answer