https://school.programmers.co.kr/learn/courses/30/lessons/150366
처음에는 MERGE 하기 위해 combine = [[(r1, c1),(r2, c2)], [...]] 와 같은 형식으로 구현한 후에 전부 돌아야하는가 하는 생각이 들었다.. 너무 효율적이지 않은데..
다른 사람의 풀이를 참고하면서 이거다! 싶은 부분들이 있었다.
- 행렬을 이중 배열이 아닌 단일 배열로 표현할 수 있다!
- 유니온 파인드 개념을 활용하면 merge와 같이 부모를 표현할 수 있다! 이전에 비슷한 문제를 풀어본 적이 있었는데 까먹었나보다..😶🌫️
행렬을 이중 배열이 아닌 단일 배열로 표현
처음에 생각했던 대로 표의 행렬을 이중배열로 표현한다면 코드를 짤 수는 있지만 MERGE, UNMERGE 부분까지 갔을 때 코드가 굉장히 복잡해진다. 아래와 같이 단일 배열로 표현하면 조금 더 간결해진다.
Union-Find(합집합 찾기)
여러 개의 노드 중 두 개의 노드를 선택해서, 현재 이 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘이다. 서로소 집합, 상호 베타적 집합(Disjoint-Set)으로도 불린다.
처음에는 각각의 노드는 자신을 부모로 갖는다. 병합될 때 부모를 합친다. 일반적으로 더 작은 값 쪽으로 합치지만(Union) 표 병합 문제 에서 제시하는 조건에 따르면,
- 두 셀 중 한 셀이 값을 가지고 있을 경우 값을 가진 값으로 병합된다.
- 혹은 두 셀 모두 값을 갖고 있다면 r1, c1 위치의 셀 값을 가진다.
위의 표와 같이 3x3 크기의 표에서 (1,2)와 (1,3)을 병합한다면 아래와 같다. (두 셀 모두 값이 있는 경우라 가정)
values = ['' for _ in range(50 * 50)]
parent = [i for i in range(50 * 50)]
def find(x):
if x != parent[x]: # x의 값(자식)과 x의 부모의 값이 같지 않으면
parent[x] = find(parent[x]) # 재귀로 계속 찾아 들어간다.
return parent[x] # 부모 값을 찾으면 반환한다.
def union(x1, x2):
root1 = find(x1) # 각 셀의 부모를 찾는다.
root2 = find(x2) # 각 셀의 부모를 찾는다.
if not values[root1] and values[root2]: # x2만 셀의 값이 존재하는 경우
parent[root1] = root2
values[root1] = values[root2]
else:
parent[root2] = root1 # ex. (1,2) 셀의 부모를 (1,3) 셀의 부모로 업데이트한다.
values[root2] = values[root1] # ex. (1,2) 셀의 값을 (1,3) 셀의 값으로 업데이트한다.
if command[0] == 'MERGE':
r1, c1, r2, c2 = map(lambda x: int(x) - 1, command[1:])
x1 = r1 * 50 + c1
x2 = r2 * 50 + c2
if parent[x1] != parent[x2]: # merge 하고자 하는 두 셀의 값이 다른 경우
union(x1, x2)전체 코드
values = ['' for _ in range(50 * 50)]
parent = [i for i in range(50 * 50)]
def find(x):
if x != parent[x]:
parent[x] = find(parent[x])
return parent[x]
def union(x1, x2):
root1 = find(x1)
root2 = find(x2)
if not values[root1] and values[root2]:
parent[root1] = root2
values[root1] = values[root2]
else:
parent[root2] = root1
values[root2] = values[root1]
def solution(commands):
answer = []
for command in commands:
command = list(command.split())
if command[0] == 'UPDATE':
if len(command) == 4:
r, c, value = command[1:]
r, c = int(r) - 1, int(c) - 1
x = r * 50 + c
rootx = find(x)
values[rootx] = value
else:
value1, value2 = command[1:]
for i in range(50 * 50):
if values[i] == value1:
values[i] = value2
elif command[0] == 'MERGE':
r1, c1, r2, c2 = map(lambda x: int(x) - 1, command[1:])
x1 = r1 * 50 + c1
x2 = r2 * 50 + c2
if parent[x1] != parent[x2]:
union(x1, x2)
elif command[0] == 'UNMERGE':
r, c = map(lambda x: int(x) - 1, command[1:])
x = r * 50 + c
rootx = find(x)
valuex = values[rootx]
nodes = []
for i in range(50 * 50):
if find(i) == rootx:
nodes.append(i)
for node in nodes:
values[node] = ''
parent[node] = node
values[x] = valuex
elif command[0] == 'PRINT':
r, c = map(lambda x: int(x) - 1, command[1:])
x = r * 50 + c
rootx = find(x)
if not values[rootx]:
answer.append('EMPTY')
else:
answer.append(values[rootx])
return answer