https://www.acmicpc.net/problem/1525
시간 1초, 메모리 32MB
input :
- 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0
output :
- 최소의 이동 횟수를 출력한다. 이동이 불가능한 경우 -1을 출력
내가 풀었다고 하기 뭐한 문제... 배우는 게 많다.
일단 0을 움직이는 것이 문제다. 이것을 3 * 3 배열로 만들 면 당연히 메모리가 터지고 이를 q에 집어넣으려 하면 더 힘들다.
검색을 해 보니 딕셔너리를 이용하는 방법이 존재했다.
배열의 모든 요소를 순서대로 딕셔너리에 저장을 하고 value에 현재까지 이동한 횟수를 저장하자.
그렇다면 딕셔너리에 문자열로 저장을 할 건데 이를 다시 꺼내서 위치를 어떻게 확인할 거냐.
우리가 받은 배열의 크기는 3 * 3 크기의 배열이다.
x를 기준으로 보면 '0'의 위치는 3의 배수에 존재하고.
y를 기준으로 보면 '0'의 위치는 3으로 얻은 나머지에 존재한다.
이를 통해서 딕셔너리에서 스왑을 할 때의 위치도 구할 수 있다.
nx 는 3의 배수에 존재하고, ny는 나머지이기 때문에
nx * 3 + ny 를 하면 문자열에서의 위치를 찾을 수 있다.
배열의 모든 아이템을 문자열로 저장하는 것.
위치를 3의 배수 / 나머지 더하기로 찾는 것 이 중요했다.
import sys
from _collections import deque
dx = [1, -1, 0, 0]
dy = [0, 0, -1, 1]
dist = dict()
aa = ''
for i in range(3):
a = sys.stdin.readline().strip().replace(' ', '')
aa += a
aa = int(aa.replace('0', '9'))
nothing = 1
q = deque()
q.append(aa)
dist[aa] = 0
while q:
status = q.popleft()
if status == 123456789:
print(dist[status])
nothing = 0
break
status_str = str(status)
where = status_str.find('9')
x, y = where // 3, where % 3
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx >= 3 or nx < 0 or ny >= 3 or ny < 0:
continue
# 문자열에서 위치 찾기.
target = nx * 3 + ny
temp = list(status_str)
temp[where], temp[target] = temp[target], temp[where]
temp = int("".join(temp))
if temp not in dist.keys():
dist[temp] = dist[status] + 1
q.append(temp)
if nothing:
print(-1)
