Idea)
0을 움직이는 좌표라 생각해봤다. 그래서 BFS를 이용하려고 했다.
그림을 예로 들면, 0이 이동할 수 있는 방향은 1 , 2, 3 세 방향이다.
움직인다는 것은 움직일 수 있는 방향의 있는 숫자와 자리를 바꾸는 것을 의미한다.
별도의 정답 리스트를 만들어 놓아서, 0이 4방향으로 숫자를 바꾸고(이동하고) 비교함으로써 index에 맞는 숫자가 들어갔는지 확인한다.
for _ in range(4) :
y좌표 이동
x좌표 이동
이동한 좌표와 원래 있던 좌표와 값을 바꾼다.
if not 방문 and 유효성 and ans[ny][nx] == board[ny][nx]
d + 1
방문처리
q에 추가 (ny,nx,nd)
else :
바뀐 값을 다시 원래대로 돌려 놓는다.board = dict()
boardStr = ''
for i in range(3):
boardStr += ''.join(sys.stdin.readline().split())
dx = (1,0,-1,0)
dy = (0,1,0,-1)
answer = "123456780"
dq = deque()
def validChk(y,x) :
return 0<=y<3 and 0<=x<3
def bfs(boardStr) :
dq.append(boardStr)
board[boardStr] = 0
while dq :
tmp = dq.popleft()
if tmp == answer :
print(board[tmp])
return
zeroIndex = tmp.find('0')
zx = zeroIndex%3
zy = zeroIndex//3
for k in range(4) :
nx = zx + dx[k]
ny = zy + dy[k]
nZeroIndex = ny*3+nx
if validChk(ny,nx) :
tmpList = list(tmp)
tmpList[zeroIndex],tmpList[nZeroIndex] = tmpList[nZeroIndex],tmpList[zeroIndex]
nxtStr = ''.join(tmpList)
if not board.get(nxtStr):
board[nxtStr] = board[tmp] + 1
dq.append(nxtStr)
print(-1)
bfs(boardStr)bfs는 방문체크를 확인할 필요가 있는데 이 문제에서는 이것을 dict() 사전 자료형을 이용하여 확인한다.
입력받은 3 x 3 배열을 문자열로 바꾸어서 저장한다.
for i in range(3):
boardStr += ''.join(sys.stdin.readline().split())
굳이 배열이 아닌 문자열로 저장하는 이유는 탐색을 진행하면서 문제에서 요구하는 "123/456/780" 을 0이 이동할 때 마다 확인해주어야 한다. 이 때 이차원배열을 사용하면 각 index를 하나씩 비교하면서 확인해야 하는데, 이를 문자열로 바꾸어 dict를 활용해서 확인한다면 더 빠르게 확인이 가능하고 제한된 메모리 안에서 해결이 가능하기 때문이다.
때문에 처음 큐에 들어가는 것은 시작좌표가 아닌 처음 board의 모양이다. (문자열)
dict에 문자열 : 횟수 형태로 저장한다.
이 문제를 공부하면서 BFS탐색으로 찾은 결과는 최단거리거나 최소횟수를 보장한다는 것이다.
BFS는 레벨1인 노드에서 레벨2인 노드를 탐색하고 레벨3인 노드를 탐색하는 순서로
탐색을 하기 떄문이다.
결과를 찾은 순간 레벨N이 었다면, N이 최단거리나 최소횟수이다.
zeroIndex = tmp.find('0')
zx = zeroIndex%3
zy = zeroIndex//3 큐에서 pop되는 것은 문자열형태이기 떄문에 이를 탐색하기 위해서는 이차원배열의 형태로 바꿔줄 필요가 있다.
먼저 문자열에서 find()를 통해서 0의 index를 찾고 이를 이차원배열의 index로 변경해준다.
012/345/678 를 보면 각 x(행)는 0/1/2인데 3으로 나눈 나머지임을 알 수 있다.
y(열)도 비슷한 개념으로 각y는 012/012/012이다. 이는 index를 3으로 나눈 몫임을 알 수 있다.
nZeroIndex = ny*3+nx 위에서 1차원의 index를 2차원으로 바꾼 것처럼 2차원의 index를 다시 1차원으로 바꾸어야 한다. 리스트에서 0을 바꾸는 작업을 해주어야 하기 때문이다.
이렇게 바꾼 리스트를 문자열로 바꾸어 큐에 저장한다.
