[백준] 1525번: 퍼즐

문제

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

1525번: 퍼즐

 

풀이

BFS(너비 우선 탐색)를 사용해 풀었습니다.

2차원으로 되어있는 배열을 문자열로 바꿔줍니다.

ex) [[1, 2, 3], [4, 5, 6], [7, 8, 9]] ➔ "123456789"

행과 열은 구하고자 하는 문자의 문자열 인덱스(pos)를 구해 행은 pos // 3, 열은 pos % 3으로 구합니다.

count 해시맵({문자열: 이동 횟수})을 사용해 이미 나온 문자열인지 확인하고 이동 횟수를 저장합니다.

※ 2차원 배열 ➔ 문자열과 해시맵이 중요 포인트입니다.

 

코드

파이썬

from collections import deque
import sys

input = sys.stdin.readline


def BFS():
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]

    queue = deque()
    count = {}
    count[start] = 0
    queue.append(start)
    while queue:
        board = queue.popleft()

        if board == "123456780":
            return count[board]

        pos = board.find('0')
        x = pos // 3
        y = pos % 3
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < 3 and 0 <= ny < 3:
                npos = nx * 3 + ny
                nboard = list(board)
                nboard[pos], nboard[npos] = nboard[npos], nboard[pos]
                nboard = "".join(nboard)
                if not count.get(nboard):
                    count[nboard] = count[board] + 1
                    queue.append(nboard)
    return -1


start = ""
for _ in range(3):
    start += "".join(input().split())
print(BFS())