문제 설명

• 메모리 제한이 32MB로 매우 작다.

입출력 예제

구현 아이디어

위 사진과 같이 상태공간 트리를 만들어 BFS로 탐색한다.
원하는 모양(마지막 칸이 빈칸이고 숫자가 오름차순으로 정렬된 형태)이 나왔을 때의 깊이를 출력한다

하지만 메모리가 매우 작기 때문에 💥2차원 리스트를 그대로 저장하면 안된다💥

이 때 사용할 수 있는 방법이 ☘️ 2차원 리스트를 문자열로 표현하는 방법 ☘️이다.

2차원 리스트 → 문자열

빈칸을 0이라고 하면,

1	0	3
4	2	5
7	8	6

은 103425786으로 나타낼 수 있다.

문자열 → 2차원 리스트

문자열을 2차원 리스트로 변환할 때는, 숫자의 위치를 좌표로 표현할 수 있어야 한다.
숫자의 위치 idx를 좌표로 변환할 때는

• 행: idx // 3
• 열: idx % 3

이 된다. 예를 들어보자.

Index	0	1	2	3	4	5	6	7	8
Element	1	0	3	4	2	5	7	8	6

이 때 3의 위치는 문자열에서는 2번째, 2차원 리스트에서는 0행 2열이다.

• 0 = 2 // 3
• 2 = 2 % 3

라는 것을 알 수 있다.

문제 풀이 과정을 정리하면 아래와 같다.

1. 2차원 리스트를 문자열 형태로 변환한다.
2. 문자열을 1차원 리스트 형태로 변환한다. (3번에서 swap을 하기 위해 필요한 과정이다)
3. 인접한 위치의 원소를 swap한 뒤, 다시 문자열로 만들에 큐에 삽입한다.
4. 큐가 빌 때까지 while문을 돌며 깊이를 계산한다.
5. 우리가 원하는 문자열( = '123456780')이 나오면 while문을 탈출하여 깊이를 출력한다.

전체 코드

import sys
from collections import deque, defaultdict

input = sys.stdin.readline

s = ''
answer = -1
visited = defaultdict(int) # 방문 여부 확인을 딕셔너리로 한다.
# ex) {'103425786': 0, '013425786': 1 ...}
dq = deque()
direction = [(0, -1), (1, 0), (0, 1), (-1, 0)]

for _ in range(3):
    s += ''.join(list(input().split()))

dq.append(s)
visited[s] = 0

while dq:
    current = dq.popleft()
	
    # 원하는 문자열을 찾으면 while문을 탈출한다
    if current == '123456780':
        answer = visited[current]
        break
	
    # 빈칸의 인덱스를 찾는다
    idx = current.index('0')
    x, y = idx // 3, idx % 3 # 문자열에서의 인덱스를 2차원 리스트 좌표로 변환
    
    for i in range(4):
        new = list(current)
        nx, ny = x + direction[i][0], y + direction[i][1]
        if nx < 0 or ny < 0 or nx >= 3 or ny >= 3:
            continue
        new[idx], new[nx*3+ny] = new[nx*3+ny], new[idx]
        new = ''.join(new)
        if new in visited.keys():
            continue

        dq.append(new)
        visited[new] = visited[current] + 1

print(answer)