BFS를 쓰면 될 것 같다는 생각은 했지만 어떻게 풀어야 할지 감이 오질 않아서...결국 서치해보고 풀었다.
3x3표라고 해서 2차원 리스트를 고집하지 말고 문자열로 바꿔서 풀 것.
그리고 딕셔너리를 만들어서 변화하는 퍼즐의 상태와, 그 상태가 만들어지는 데까지 필요한 이동 횟수를 저장하는 것이 핵심이었다.
from collections import deque
target = ""
for i in range(3):
# 빈 칸을 지우고 이어붙이기
target += input().replace(' ','')
# key: 각 퍼즐의 상태를 문자열로 만든 것
# value: 그 상태에 도달하는 데에 필요한 이동 횟수
visited = dict()
# 초기상태가 되기 위한 이동횟수는 0
visited[target]=0
dx = [-1,1,0,0]
dy = [0,0,-1,1]
def bfs(start):
queue = deque([start])
while queue:
v = queue.popleft()
# 목표 상태에 도달했으면 이동 횟수를 리턴
if v=="123456780":
return visited[v]
# 문자열에서 0의 인덱스를 찾음
idx = v.find('0')
# 3x3표에서 0이 위치한 곳의 행과 열
x, y = idx//3, idx%3
for i in range(4):
nx = x+dx[i]
ny = y+dy[i]
# 이동할 수 있다면
if 0<=nx<3 and 0<=ny<3:
# 이동한 곳의 문자열에서의 인덱스를 구함
nidx = nx*3+ny
# 문자열의 내용(=퍼즐의 내용)을 변경하기 위해 리스트로 변경
nstr = list(v)
# 0과 자리를 swap
nstr[idx],nstr[nidx] = nstr[nidx],nstr[idx]
# 리스트를 문자열로 바꿈
nstr = ''.join(nstr)
# 딕셔너리에 해당 문자열의 값이 없다면(퍼즐의 상태가 처음 나온 거라면)
# 기존 이동 횟수+1을 해주고 큐에 다시 넣음
if nstr not in visited:
visited[nstr] = visited[v]+1
queue.append(nstr)
# 여기까지 리턴되지 않았다는 건 목표 상태에 도달할 수 없다는 뜻이므로 -1을 리턴
return -1
print(bfs(target))
'[BOJ] - Python' 카테고리의 다른 글
[백준] 14503 : 로봇 청소기 python (0) | 2023.08.24 |
---|---|
[백준] 2468 : 안전 영역 python (0) | 2023.08.22 |
[백준] 10451 : 순열 사이클 python (0) | 2023.08.19 |
[백준] 11724 : 연결 요소의 개수 python (0) | 2023.08.18 |
[백준] 2644 : 촌수계산 python (0) | 2023.08.18 |