[백준(BOJ)] #1525- 퍼즐 (파이썬, PyPy3)

문제

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

1525번: 퍼즐

 

---

문제 풀이

BFS 알고리즘 적용하여 해결

 

1) 입력받은 board를 문자열로 변환

2) 완성된 퍼즐 모양이 나올 때까지 문자열의 인덱스를 조정해가면서 탐색. 퍼즐 모양이 나오면 움직인 횟수를 출력하고 퍼즐 모양을 만들 수 없으면 -1 출력

 

위와 같은 모양의 board에서 빈칸(0)을 움직이면서 퍼즐을 완성시키는 것이 목적입니다. BFS 알고리즘을 적용하여 퍼즐을 완성시키기 위해 2차원 모양의 board를 문자열로 변환시킵니다.

 

순서에 맞게 문자열로 변환시키면 문자열은 "103425786"이 됩니다.

 

완성된 퍼즐 모양은 좌측 상단의 그림 모양과 같고, 이를 문자열로 나타내면 "123456780"입니다. 문자열 "103425786"을 "123456780"으로 바꿔주면 되는 것입니다. 1차원 모양의 문자열과 2차원 모양의 board의 인덱스를 고려하여 움직일 수 있습니다.

 

뭔가 규칙이 보이시나요? 

 

1차원 문자열에서의 인덱스를 3으로 나눈 몫이 2차원 board에서의 행이 되고, 3으로 나눈 나머지가 열이 됩니다. 이를 반대로 하면 2차원 board에서 행 x 3 + 열이 1차원 문자열에서의 인덱스가 되는 것이죠.

 

문자열 -> board

행: index // 3
열: index % 3

board -> 문자열

인덱스: 3 * 행 + 열

 

이 원리를 사용하여 나올 수 있는 퍼즐 모양을 탐색하고, "123456780"모양의 퍼즐이 나오게 되면 움직인 횟수를 출력하고 종료합니다. 

 

---

구현

코드

import sys
from collections import deque
input = sys.stdin.readline

# 시작 위치 반환
def get_list_to_str(board):
    s = ''
    for i in range(3):
        for j in range(3):
            s += board[i][j]
    return s

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

    # 완성된 퍼즐 모양
    target = '123456780'
    puzzle_set = set()
    dq = deque()

    dq.append((board, 0))
    puzzle_set.add(board)

    while dq:
        board, cnt = dq.popleft()
        # 퍼즐이 완성되면 횟수 반환
        if board == target:
            return cnt

        z = board.index('0')
        # 2차원 board에서 0이 있는 인덱스 
        tx = z // 3
        ty = z % 3

        for k in range(4):
            x = tx + dx[k]
            y = ty + dy[k]
            if 0 <= x < 3 and 0 <= y < 3:
                # 1차원 인덱스로 변환하여 0의 자리를 교체
                nz = 3 * x + y
                nboard = list(board)
                nboard[z], nboard[nz] = nboard[nz], nboard[z]
                nboard = "".join(nboard)

                # 이미 탐색한 퍼즐 모양이라면 큐에 넣지 않음
                if nboard not in puzzle_set:
                    dq.append((nboard, cnt + 1))
                    puzzle_set.add(nboard)
    # 퍼즐을 완성시키지 못하는 경우 -1 반환
    return -1


if __name__ == "__main__":
    board = [list(input().split()) for _ in range(3)]
    board = get_list_to_str(board)
    print(bfs(board))

 

결과