[Python] Baekjoon - 1525. 퍼즐

퍼즐 문제는 1에서 8까지의 숫자로 채워진 3x3 퍼즐을 맞추는 문제이다. 퍼즐을 움직이는 최소 횟수를 구하기 위해 그래프 탐색 알고리즘 중 너비 우선 탐색을 사용하여 풀 수 있다. 난이도는 골드 2이다. 메모리가 초과되지 않도록 방문 확인 배열을 선언하는 것이 중요하다.

 

백준 1525번 퍼즐 문제 정보

알고리즘 분류

- 그래프 탐색 (BFS)

난이도

- 골드 2

 

퍼즐 문제 요약

1~8로 채워진 3x3 퍼즐이 있는데 나머지 한 칸은 빈칸이다. 빈칸의 상하좌우 칸만 빈칸으로 이동할 수 있을 때, 왼쪽 위에서부터 1 2 3 4 5 6 7 8 (빈칸) 상태가 되도록 움직이는 최소 횟수를 구하는 문제다.

 

문제 풀이 과정

• 최소 횟수를 구하는 문제이므로 BFS를 이용한다.
• 무한루프에 빠지지 않기 위해(답이 없는 경우를 확인하기 위해) visited 배열이 필요하다. 메모리를 초과하지 않는 선에서 visited 배열을 선언해야 한다.
  • 9차원 배열 -> 9^9 = 약 45MB (X)
  • 9! x 9자리 문자열 = 약 2MB (O)

 

자세한 풀이

• 매 상태를 9자리 문자열로 나타낸다.
• 빈칸의 -1, +1, -3, +3칸과 swap 해가며 BFS를 시행한다.
  • 첫 제출은 -1, +1로 행이 변경되는 칸을 고려하지 않아서 틀렸다.
  • 2,3,5,6 위치 숫자에 대한 예외 처리를 통해 정답을 맞혔다(질문 검색을 참고하였다).

 

 

코드

from collections import deque


def bfs():
    global board, visited
    dx = [-1, 1, -3, 3]
    queue = deque()

    queue.append((board, 0))
    visited.add(board)

    while len(queue) > 0:
        here_state, here_cnt = queue.popleft()
        here_blank = here_state.index('0')

        # 정답이 되면 종료
        if here_state == '123456780':
            return here_cnt

        for d in range(4):
            # +1 또는 -1을 해줄때 행이 변하면 안됨
            if (d == 0 and here_blank in (3, 6)) or (d == 1 and here_blank in (2, 5)):
                continue

            dest = here_blank + dx[d]
            if 0 <= dest < 9:
                # blank 위치랑 dest 위치 숫자 swap
                new_state = ''
                target_num = here_state[dest]
                for i, x in enumerate(here_state):
                    if i == here_blank:
                        new_state += target_num
                    elif i == dest:
                        new_state += '0'
                    else:
                        new_state += x
                # 방문한 적 없는 배치면 방문
                if new_state not in visited:
                    queue.append((new_state, here_cnt + 1))
                    visited.add(new_state)

    return -1


if __name__ == '__main__':
    board = ''
    for _ in range(3):
        board += ''.join(input().split())
    visited = set(board)
    print(bfs())