프로그래머스 표 병합 (LV3)[2023 KAKAO BLIND RECRUITMENT]
문제
문제를 캡쳐해오거나 긁어오기에는 너무 길어서,
링크로 대체합니다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
def solution(commands):
answer = []
merge=dict()
value = dict()
for i in range(1,51):
for j in range(1,51):
merge[(i,j)]=50*(i-1)+j
for i in range(1,51):
for j in range(1,51):
value[(i,j)]="EMPTY"
for state in commands:
state_list = state.split(" ")
if (state_list[0] == "UPDATE" and len(state_list) == 4):
x = int(state_list[1])
y = int(state_list[2])
data = state_list[3]
bechanged=merge[(x,y)]
for k,v in merge.items():
if(v==bechanged):
value[k]=data
elif (state_list[0] == "UPDATE" and len(state_list) == 3):
for k,v in value.items():
if (v == state_list[1]):
value[k] = state_list[2]
elif (state_list[0] == "MERGE"):
r1 = int(state_list[1])
c1 = int(state_list[2])
r2 = int(state_list[3])
c2 = int(state_list[4])
if ((r1, c1) == (r2, c2)):
continue
# 인접하든안하든 상관 x
# 두셀 중하나만 존재할경우
if (value[(r1,c1)]=="EMPTY" and value[(r2, c2)] !="EMPTY"):
change=merge[(r1,c1)]
tobe=merge[(r2,c2)]
for k,v in merge.items():
if(v==change):
merge[k]=tobe
value[k]=value[(r2,c2)]
elif (value[(r1,c1)]!="EMPTY" and value[(r2, c2)] =="EMPTY"):
change=merge[(r2,c2)]
tobe=merge[(r1,c1)]
for k,v in merge.items():
if(v==change):
merge[k]=tobe
value[k]=value[(r1,c1)]
# 두셀모두 값이 없을경우
elif (value[(r1,c1)]=="EMPTY" and value[(r2, c2)] =="EMPTY"):
change=merge[(r2,c2)]
tobe=merge[(r1,c1)]
for k,v in merge.items():
if(v==change):
merge[k]=tobe
# 두셀모두 값이 있을경우
else:
change=merge[(r2,c2)]
tobe=merge[(r1,c1)]
for k,v in merge.items():
if(v==change):
merge[k]=tobe
value[k]=value[(r1,c1)]
elif (state_list[0] == "UNMERGE"):
r1 = int(state_list[1])
c1 = int(state_list[2])
finded=merge[(r1,c1)]
temp=value[(r1,c1)]
for k,v in merge.items():
if(v==finded):
value[k]="EMPTY"
merge[k]=(k[0]-1)*50+k[1]
value[(r1,c1)]=temp
else:
r1 = int(state_list[1])
c1 = int(state_list[2])
answer.append(value[(r1,c1)])
return answer
풀이
merge부분에서 서로 병합되어있다는 정보를 기록하는 방법을 제외하고는, 주어진 조건에 따라 코드를 작성하는 기본적인 구현 문제이다.
서로 병합이 되어있다는 정보를 어떻게 관리해야될까? 병합이 되어있다는 건, 서로의 부모가 동일한 요소로부터 왔다는 걸 확인해보면 된다.
그러면 알고리즘을 좀 공부하신 분들이라면 유니온파인드알고리즘을 떠올릴 것이다.
기본적인 구현은 아래와 같다
유니온 파인드
상호 배타적 집합, Disjoin-set(서로소 집합) 이라고도 부른다. 여러 노드가 존재할 때 어떤 두 개의 노드를 같은 집합으로 묶어 주고, 어떤 두 노드가 같은 집합에 있는지 확인하는 알고리즘이다.
알고리즘 이름 그대로, Union 연산과 Find 연산을 수행할수 있도록 구현한다.
Union: 서로 다른 두 개의 집합을 하나의 집합으로 병합하는 연산을 말한다. 이 자료구조에서는 상호 배타적 집합만을 다루므로 Union 연산은 합집한 연산과 같다.
Find: 하나읜 원소가 어떤 집합에 속해있는지를 판단한다.
코드로 구현하면 아래와 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# find함수 정의
def find(x):
# 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
# 부모 노드가 자기자신이다 => 루트 노드이다
if parent[x] != x:
return find(parent[x])
return x
# 두 원소가 속한 집합을 합치기
def union(a, b):
a = find(a)
b = find(b)
# 부모를 항상 더큰 값으로 둘지, 더 작은 값으로 둘지는 자유이다
# 여기서는 더 작은 값은 부모로 두었다.
if a < b:
parent[b] = a
else:
parent[a] = b
# 기본 초기화시 각노드의 값을 부모값으로 선언
# parent[v]=v
실제 접근법
물론 유니온파인드로 접근해서 풀어도 상관없다. 필자도 유니온파인드로 처음에 접근했다가, 더 간단한 접근방법이 있어서 설명해보려한다.
어차피 50 * 50 = 2500 개의 격자판이므로, 그렇게 많지않고 충분히 관리할 수 있는 크기이므로, 가로 50, 세로 50의 격자판에대한 좌표 딕셔너리를 선언한다음, 각 좌표값으로는 인덱스에 해당하는 값을 할당해준다.
즉 (1,1) ~ (1,50) 까지의 Key에대한 Value값은 1~50을, (2,1) ~ (2,50) 까지의 Key에대한 Value값은 51~100을 할당해준다.
이렇게 할당해준다음, 만약 merge, 즉 부모가 같아진다면, 해당 좌표에대한 value값을 주어진 조건에 맞춰 통일시켜준다.
아래 코드는 격자판의 각 좌표를 Key로, 각 좌표의 인덱싱값을 Value로 가지는 딕셔너리를 선언하는 코드이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
merge=dict()
value = dict()
# 좌표마다 인덱스값을 부여해서 merge상태를 관리한다
for i in range(1,51):
for j in range(1,51):
merge[(i,j)]=50*(i-1)+j
#이 딕셔너리는 실제로 해당좌표에 값을 관리하는 딕셔너리이다
#기본 값은 EMPTY로 초기화 해준다.
for i in range(1,51):
for j in range(1,51):
value[(i,j)]="EMPTY"
문제에서 얻은 것
격자판의 좌표가 너무 많지 않다면, 부모(뿌리)가 같은지를 확인할때는 굳이 유니온파인드 알고리즘을 사용하지않아도, 각 좌표의 인덱스값을 부여함으로서 해결할 수 있다.