[백준] 1525 : 퍼즐 python

 

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))