문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/150366
문제 파악
문제가 길다.
- 표의 크기 50 x 50 고정
- 셀 비어있음, 문자열 값 가질 수 있음, 다른 셀과 병합될 수 있음
명령어 기능 구현하려고 한다.
1. "UPDATE r c value"
= (r,c) 위치에 셀 값을 value로 업데이트
2. "UPDATE value1 value2"
= value1을 값으로 가지는 모든 셀 -> value2로 변경
3."MERGE 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" 출력
예시 흐름
해답
def solution(commands):
N = 50
SIZE = N * N
parent = [i for i in range(SIZE)]
value = [""] * SIZE # 각 루트의 값
def idx(r, c): # (r,c) 좌표를 0~2499의 숫자 인덱스로 바꾸는 함수
r = int(r)
c = int(c)
return (r - 1) * N + (c - 1)
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(a, b):
ra, rb = find(a), find(b)
if ra == rb:
return ra
parent[rb] = ra
# 병합 후 값 결정
if value[ra] and not value[rb]:
chosen = value[ra]
elif not value[ra] and value[rb]:
chosen = value[rb]
else:
chosen = value[ra]
value[ra] = chosen
value[rb] = ""
return ra
answer = []
def UpdateRCValue(parts):
_, r, c, v = parts
root = find(idx(r, c))
value[root] = v
def UpdateV1V2(parts):
_, v1, v2 = parts
if v1 == v2:
return
for i in range(SIZE):
if parent[i] == i and value[i] == v1:
value[i] = v2
def Merge(parts):
_, r1, c1, r2, c2 = parts
id1 = idx(r1, c1)
id2 = idx(r2, c2)
root1 = find(id1)
root2 = find(id2)
if root1 != root2:
union(root1, root2)
def Unmerge(parts):
_, r, c = parts
id0 = idx(r, c)
root = find(id0)
saved = value[root]
group = [i for i in range(SIZE) if find(i) == root]
for i in group:
parent[i] = i
value[i] = ""
value[id0] = saved
def Print(parts):
_, r, c = parts
root = find(idx(r, c))
answer.append(value[root] if value[root] else "EMPTY")
# -------- if-elif로 명령 분기 --------
for line in commands:
parts = line.split()
op = parts[0]
if op == "UPDATE":
if len(parts) == 4:
UpdateRCValue(parts)
else:
UpdateV1V2(parts)
elif op == "MERGE":
Merge(parts)
elif op == "UNMERGE":
Unmerge(parts)
elif op == "PRINT":
Print(parts)
return answer차근 차근 문제에 흐름에 따라 코드를 짜나가야하는 구현 문제였다.
merge,unmerge 명령어 구현에 Union-Find 를 떠올리지 못했다.
처음엔 단순히 2차원 배열 matrix[r][c]에 값을 직접 넣고 갱신하면 되겠다고 생각했지만,
막상 MERGE와 UNMERGE를 구현하려고 하니 문제가 터졌다.
단순한 인접 셀 병합이 아니라,
“하나의 그룹처럼 움직이는 셀 묶음”을 관리해야 했다.
예를 들어 (1,1)과 (1,2)를 합치고, 그다음 (1,2)와 (2,2)를 합치면
결국 (1,1), (1,2), (2,2) 세 칸이 모두 한 그룹으로 묶여야 한다.
이 관계를 단순 배열로 처리하려니 점점 복잡해졌다.
그때 떠올려야 했던 게 바로 Union-Find (Disjoint Set, 서로소 집합) 구조였다.
이걸 쓰면 각 셀이 어느 그룹(루트)에 속해 있는지 빠르게 관리할 수 있고,
병합(MERGE)은 union, 그룹 대표 찾기(값 조회)는 find로 단순화된다.
Frontend Engineers