https://school.programmers.co.kr/learn/courses/30/lessons/150366
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제 설명
당신은 표 편집 프로그램을 작성하고 있습니다.
표의 크기는 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 함수를 완성해 주세요.
처음엔 조금 헤매었는데, 그래프/트리 자료구조를 사용해서 풀 수 있었다.
(1, 1), (1, 2), (1, 2)... (2, 1), (2, 2).. (50, 50)의 노드들이 있고, MERGE 명령어가 나오면 간선으로 두 노드를 연결하고 UNMERGE 명령어가 나오면 두 노드를 이은 간선을 끊어내는 작업이 필요하다.
그래프 탐색 과정에는 덱 자료구조 또한 사용하였다.
1. UPDATE
UPDATE 에는 두 가지 방식이 있는데, 2번과 같은 경우에는 표의 크기가 최대 50x50이므로 그대로 완전 탐색을 진행한다.
1번과 같은 경우에는 (r, c) 노드와 연결된 모든 노드들의 값을 v로 바꾸어준다. 값을 바꾼 노드의 경우는 방문 표시를 해준다.
def change_value(cur, v, connect, value): # cur과 연결된 모든 셀들의 값들을 v로 바꾼다.
q = deque([cur])
visited = {}
for i in range(1, 51):
for j in range(1, 51):
visited[(i, j)] = False
while q:
r, c = q.popleft()
value[(r, c)] = v
visited[(r, c)] = True
for i, j in connect[(r, c)]:
if not visited[(i, j)]:
q.append([i, j])
return connect, valueif cmd[0] == 'UPDATE':
if len(cmd) == 4: # 1. (r, c)와 연결된 모든 셀들의 값을 바꾼다.
r, c, v = int(cmd[1]), int(cmd[2]), cmd[3]
connect, value = change_value((r, c), v, connect, value)
else: # 2. 모든 셀을 탐색하고 v1을 v2로 바꾼다.
v1, v2 = cmd[1], cmd[2]
for i in range(1, 51):
for j in range(1, 51):
if value[(i, j)] == v1:
value[(i, j)] = v2
2. MERGE
서로의 셀의 위치 정보를 connect에 담는다.
- 두 셀 중 한 셀이 값을 가지고 있을 경우 병합된 셀은 그 값을 가지게 됩니다.
- 두 셀 모두 값을 가지고 있을 경우 병합된 셀은 (r1, c1) 위치의 셀 값을 가지게 됩니다.
문제의 제시 조건을 확인해보면, 만약 (r2, c2)만 값을 가지고 있다면 병합된 셀들은 (r2, c2)의 값들을 가지게 되고, 그렇지 않을 때에 (r1, c1)의 값이 존재하는 경우에는 병합된 셀들은 (r1, c1)의 값을 가지게 된다고 해석할 수 있다.
elif cmd[0] == 'MERGE': # 3. 두 셀을 병합하고 조건에 따라 적절히 연결된 모든 셀들의 값을 바꾼다.
r1, c1, r2, c2 = int(cmd[1]), int(cmd[2]), int(cmd[3]), int(cmd[4])
connect[(r1, c1)].append((r2, c2))
connect[(r2, c2)].append((r1, c1))
if value[(r1, c1)] == 'EMPTY' and value[(r2, c2)] != 'EMPTY':
connect, value = change_value((r2, c2), value[(r2, c2)], connect, value)
elif value[(r1, c1)] != 'EMPTY':
connect, value = change_value((r1, c1), value[(r1, c1)], connect, value)
3. UNMERGE
(r, c) 셀은 그 값을 유지하기 위해 연결을 끊는 과정 이전에 값을 따로 저장해 둔다.
cut_off_connect 함수를 통해 덱에서 노드의 위치 정보를 꺼내면, 그 노드와 연결된 노드들의 정보를 모두 덱에 담은 뒤, 연결 노드와의 정보를 지운다. 연결되었던 모든 셀의 값들은 'EMPTY'로 초기화한다.
def cut_off_connect(cur, connect, value): # cur과 연결된 모든 셀들의 연결을 끊어냄과 동시에 값을 비운다.
q = deque([cur])
while q:
r, c = q.popleft()
value[(r, c)] = 'EMPTY'
for i, j in connect[(r, c)]:
q.append([i, j])
connect[(r, c)] = []
return connect, valueelif cmd[0] == 'UNMERGE': # 4. 모든 셀들의 연결을 끊으며 초기 상태로 되돌린다. (r, c)의 값은 유지된다.
r, c = int(cmd[1]), int(cmd[2])
v = value[(r, c)]
connect, value = cut_off_connect((r, c), connect, value)
value[(r, c)] = v
4. PRINT
value 딕셔너리에 저장된 (r, c) 셀의 값을 출력한다.
else: # 5. (r, c) 위치의 셀의 값을 출력한다.
r, c = int(cmd[1]), int(cmd[2])
answer.append(value[(r, c)])
<< 전체 코드 >>
from collections import deque
def change_value(cur, v, connect, value):
q = deque([cur])
visited = {}
for i in range(1, 51):
for j in range(1, 51):
visited[(i, j)] = False
while q:
r, c = q.popleft()
value[(r, c)] = v
visited[(r, c)] = True
for i, j in connect[(r, c)]:
if not visited[(i, j)]:
q.append([i, j])
return connect, value
def cut_off_connect(cur, connect, value):
q = deque([cur])
while q:
r, c = q.popleft()
value[(r, c)] = 'EMPTY'
for i, j in connect[(r, c)]:
q.append([i, j])
connect[(r, c)] = []
return connect, value
def solution(commands):
answer = []
connect, value = {}, {}
for i in range(1, 51):
for j in range(1, 51):
connect[(i, j)] = []
value[(i, j)] = 'EMPTY'
for cmd in commands:
cmd = cmd.split()
if cmd[0] == 'UPDATE':
if len(cmd) == 4:
r, c, v = int(cmd[1]), int(cmd[2]), cmd[3]
connect, value = change_value((r, c), v, connect, value)
else:
v1, v2 = cmd[1], cmd[2]
for i in range(1, 51):
for j in range(1, 51):
if value[(i, j)] == v1:
value[(i, j)] = v2
elif cmd[0] == 'MERGE':
r1, c1, r2, c2 = int(cmd[1]), int(cmd[2]), int(cmd[3]), int(cmd[4])
connect[(r1, c1)].append((r2, c2))
connect[(r2, c2)].append((r1, c1))
if value[(r1, c1)] == 'EMPTY' and value[(r2, c2)] != 'EMPTY':
connect, value = change_value((r2, c2), value[(r2, c2)], connect, value)
elif value[(r1, c1)] != 'EMPTY':
connect, value = change_value((r1, c1), value[(r1, c1)], connect, value)
elif cmd[0] == 'UNMERGE':
r, c = int(cmd[1]), int(cmd[2])
v = value[(r, c)]
connect, value = cut_off_connect((r, c), connect, value)
value[(r, c)] = v
else:
r, c = int(cmd[1]), int(cmd[2])
answer.append(value[(r, c)])
return answer