문제
접근
처음에 문제를 보고 막막했다.
BFS로만 접근해선 해결할 수 없어 보였다.
3 x 3 배열안에서 이동해가며 원하는 조건을 만족시켜야 하는데,
기존 알아왔던 BFS와 다르게 이미 방문했는지 어떻게 체크할 수 있을지 고민하게 된 문제이다.
현재 위치를 기준으로 방문 여부를 체크할 수는 없다.
이렇게 하면 최대 9번만 움직일 수 있다는 얘기가 되고, 같은 위치에 다시 방문하지 못한다.
하지만 이 문제는 주어지는 수들이 어떻게 변하는지에 따라 같은 자리에 다시 와야할 일이 생긴다.
결국 방문 여부를 위치가 아닌 다른 것으로 해야한다는 생각이 들었고, 여기서 BFS 특징과 엮을 수 있단 생각에 미쳤다.
BFS는 최초 방문한 점이 항상 최단 거리로 방문했음을 보장할 수 있다.
문제에서 주어지는 3 X 3 배열의 숫자들을 묶어서 하나의 위치로 보면 되지 않을까?
예를 들어,
1 2 5
3 4 6
8 7 0
이라는 배열이 주어지면 이는 125346870 이라는 위치가 되는 것이다.
이 위치를 딕셔너리의 key로 주고 value로 몇 번만에 이 위치를 오게됬는지 준다면 문제를 해결할 수 있을 것 같다.
신선했던 문제이고, 기존에 사용하던 BFS를 다른 방식으로도 사용할 수 있단 것을 알려준 문제이다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
from collections import deque
dx = [0,0,-1,1]
dy = [1,-1,0,0]
BOARD_SIZE = 3
def bfs(start):
q = deque()
q.append(start)
board[start] = 0
while q:
now = q.popleft()
if now == '123456780':
return board[now]
loc = now.find('0')
nowx, nowy = loc % BOARD_SIZE, loc // BOARD_SIZE
for x, y in zip(dx, dy):
nx = x + nowx
ny = y + nowy
nloc = ny * 3 + nx
if nx < 0 or nx >= BOARD_SIZE or ny < 0 or ny >= BOARD_SIZE:
continue
nowList = list(now)
nowList[loc], nowList[nloc] = nowList[nloc], nowList[loc]
nxt = ''.join(nowList)
if not board.get(nxt):
board[nxt] = board[now] + 1
q.append(nxt)
return -1
board = {}
nowInput = ''
for i in range(BOARD_SIZE):
nowInput += ''.join(input().split(' '))
print(bfs(nowInput))