[문제 바로가기] https://www.acmicpc.net/problem/1525
📌문제 설명
3×3 표에 다음과 같이 수가 채워져 있다. 오른쪽 아래 가장 끝 칸은 비어 있는 칸이다.
어떤 수와 인접해 있는 네 개의 칸 중에 하나가 비어 있으면, 수를 그 칸으로 이동시킬 수가 있다. 물론 표 바깥으로 나가는 경우는 불가능하다. 우리의 목표는 초기 상태가 주어졌을 때, 최소의 이동으로 위와 같은 정리된 상태를 만드는 것이다. 다음의 예를 보자.
가장 윗 상태에서 세 번의 이동을 통해 정리된 상태를 만들 수 있다. 이와 같이 최소 이동 횟수를 구하는 프로그램을 작성하시오.
입력
세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다.출력
첫째 줄에 최소의 이동 횟수를 출력한다. 이동이 불가능한 경우 -1을 출력한다.
💡 문제 풀이
메모리 제한이 매우 엄격한(?)문제다. 따라서 어떠한 처리도 없이 2차원 배열을 그대로를 사용하는 것은 있다.
메모리 제한을 해결하기 위해서 2차원 배열을 문자열로 변경하였다.
주어진 퍼즐을 행 순서대로 문자열로 추가한다
ex) '103425786'
그리고 최소한의 이동으로 '정리된 상태'를 만들어야 하기 때문에 BFS를 이용하였다.
step 1)
변수 선언
- puzzle : 주어진 3x3배열을 문자열화 시킨 값
- step : "puzzle:이동횟수" 원소를 담을 딕셔너리
- queue : BFS 이용시 사용할 큐
step 2)
주어진 3x3 배열을 문자열로 바꾼다. → puzzle
초기상태의 puzzle을 이용하여 step, queue를 초기화한다.
step = {puzzle : 0}
queue = deque([puzzle])step 3)
BFS를 이용하여 '정리된 상태'의 퍼즐모양을 찾는다.
※퍼즐을 문자열로 바꿨기 때문에 찾으려는 문자열은 '123456780'이다.
먼저 0을 다른 숫자와 바꾸기 위해서는 3x3 배열을 벗어나면 안되기 때문에 4방향 탐색이 필요하다.
비록 문자열로 바꾸었지만 인덱스를 이용하여 행, 열 좌표를 계산할 수 있다.
'0'의 위치(인덱스)를 찾은 다음 아래와 같이 계산하여 행, 열 좌표를 구한다.
- 행 : '0'의 인덱스를 3으로 나눈 몫
- 열 : '0'의 인덱스를 3으로 나눈 나머지
ex) '103425786'에서 '0'의 인덱스는 1이며 (행, 열) 좌표는 (0, 1)이다.
좌표를 구했으면 4방향을 탐색하여 3x3 배열을 벗어나는지 파악한다.
step 4)
3x3 배열을 벗어나지 않으면 해당 숫자와 자리를 바꾼다.
자리를 변경하기 위해서 문자열을 1차원 배열로 바꿔서 변경한다.
※문자열은 값 수정 X
바꾼 결과를 다시 문자열로 변경한 후 step에 해당 문자열이 존재하는지 파악한다. (딕셔너리이므로 keys() 활용)
만약, 해당 문자열이 존재하지 않는다면 step과 queue에 각각 알맞은 값을 추가한다.
- step → "이동후 퍼즐(new_p): 이전퍼즐의 이동횟수+1"
- queue → 이동후 퍼즐(new_p)
step 5)
queue에 원소가 남아있을 때 까지 '정리된 상태'를 만들 수 있다면 이동횟수를 return하고 그렇지 않으면 -1을 return 한다.
코드는 다음과 같다.
import sys
from collections import deque
d = [(-1, 0), (0, 1), (1, 0), (0, -1)]
def bfs():
while queue:
p = queue.popleft()
if p == '123456780': # '123456789' - 정리된 상태가 되면 종료
return step[p]
zero = p.find('0') # '0'의 위치를 찾는다.
r, c = zero // 3, zero % 3 # '0'의 인덱스를 이용해 행, 열 좌표를 계산한다.
for idx in range(4): # 4방향 탐색을 통해서 3x3 배열 밖에 벗어나지 않는지 확인한다.
nr = r + d[idx][0]
nc = c + d[idx][1]
if 0 <= nr < 3 and 0 <= nc < 3:
p_list = list(p) # string → list
p_list[zero], p_list[nr*3+nc] = p_list[nr*3+nc], p_list[zero] # 원소를 바꾼다.
new_p = ''.join(p_list) # list → string
if new_p not in step.keys(): # 새로운 퍼즐(new_p)이 step의 key에 없다면 추가한다.(이동횟수+1)
step[new_p] = step[p] + 1
queue.append(new_p)
return -1 # 찾지못하면 -1 return
inputs = [list(map(int, sys.stdin.readline().split())) for _ in range(3)]
puzzle = '' # inputs의 3x3 배열을 한줄로 나열
for r in range(3):
row = ''
for c in range(3):
row += str(inputs[r][c])
puzzle += row
step = {puzzle : 0} # dictionary를 이용하여 "퍼즐:이동횟수" 형식으로 key-value를 넣는다.
queue = deque([puzzle]) # queue
print(bfs())많이 고민하고 어려워했던 문제인 만큼 좋은 알고리즘 문제였다고 생각한다. 👍
