백준 퍼즐 1525 BFS

https://www.acmicpc.net/problem/1525

1525번: 퍼즐

 

• 2차원 배열 형태의 퍼즐을 문자열로 만들어준다는 것이 포인트!
• 0의 위치를 바꿔나가면서 새로 생성된 그래프를 또다시 문자열로 만들어주고 "123456780"에 해당하는지 비교해줘야 함.
• 2차원 배열에서의 x, y 좌표값은 문자열에서 index 값을 3으로 나눈 몫과 나머지로 구할 수 있음.

 

from collections import deque

graph = ""
for i in range(3):
    graph += "".join(list(input().split())) # 그래프를 문자열로 만들어준다 

queue = deque([graph])
visited = dict()    # key: 그래프, value: 해당 그래프를 만들기 위해 퍼즐을 옮긴 횟수 
dx = [1,-1,0,0]
dy = [0,0,-1,1]

def bfs():
    visited[graph] = 0

    while(queue):
        target = queue.popleft()

        if target == "123456780":
            return visited[target]
        
        idx = target.find("0")  # 그래프에서 빈 공간인 0의 위치
        x = idx // 3            # 2차원 배열일 때 빈 공간의 x 좌표
        y = idx % 3             # y 좌표

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < 3 and 0 <= ny < 3:
                n = nx * 3 + ny     # 0 주변의 퍼즐값 
                list_target = list(target) # 문자열 그래프를 리스트로 변환
                # swap
                # 빈 공간의 인덱스에 현재 좌표를 넣고 현재 좌표에 빈 공간의 인덱스 값을 넣는다.
                list_target[idx], list_target[n] = list_target[n], list_target[idx]
                new_target = "".join(list_target) # 리스트 퍼즐을 문자열로 변환

                # 현재 그래프 모양을 갖는 key 값이 없다면
                if not visited.get(new_target):
                    visited[new_target] = visited[target] + 1   # 횟수 갱신
                    queue.append(new_target)    # 탐색 추가

    # 탐색이 끝나도 정리된 상태가 안된다면 -1 리턴
    return -1

print(bfs())