BOJ 1525 퍼즐

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)