[백준] 1525 퍼즐

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 접근 및 이해

비어있는 칸의 이동을 위해 DFS 탐색을 시도하였으나, 최소 이동 가능한 횟수를 우선적으로 구하는 것이 아니라 이동이 가능한 모든 경우를 탐색하게 됩니다.

모든 경우를 탐색하므로 시간 초과 문제가 발생할 수 있었습니다.

이로 인해 BFS 탐색을 이용하였습니다.

 

보드판의 특정 상황을 탐색한적이 있는지 확인이 필요했습니다.

특정 좌표의 원시값을 방문 여부로 처리 하는 것이 아니라 2차원 배열의 전체 상황을 기록이 필요하였습니다.

특정 상황의 탐색 여부를 확인하기 위해 2차원 배열을 저장할 수 없으므로, 2차원 배열의 상황을 풀어서 하나의 문자열로 나타냈습니다.

문자열을 이용하여 방문 여부를 확인하였습니다.

2) 알고리즘

• BFS
• 문자열

3) 풀이 코드

사용 언어 - Python

import sys
from collections import deque
sys.stdin = open('input.txt')


# 문자열로 된 보드판의 비어있는 좌표값 반환
def get_coors(board: str):
    idx = board.find('0')
    # 행, 열 반환
    return idx // 3, idx % 3


# 좌표를 이동하고 문자열로 변환하여 반환
def move_coors(board: list, from_y: int, from_x: int, to_y: int, to_x: int) -> str:
    # 좌표들을 문자열의 인덱스로 변경
    from_idx = from_y * 3 + from_x
    to_idx = to_y * 3 + to_x

    # 이동 대상이 되는 인덱스의 값들 서로 변경
    board[from_idx], board[to_idx] = board[to_idx], board[from_idx]
    return ''.join(board)


# BFS 탐색
def solution(board: str) -> None:
    q = deque([(board, 0)])

    while q:
        board, ans = q.popleft()

        # 정답을 찾았다면, 변경 횟수 반환
        if board == '123456780':
            return ans

        # 문자열에서 비어있는 좌표값 구하기
        y, x = get_coors(board)
        for k in range(4):
            r = y + dr[k]
            c = x + dc[k]

            if 0 <= r < 3 and 0 <= c < 3:
                # 비어있는 곳을 좌표 이동시키기
                new_board = move_coors(list(board), y, x, r, c)
                # 이전에 탐색했던 경우가 아니라면, 다음 탐색 위해 추가
                if new_board not in visited:
                    q.append((new_board, ans+1))
                    visited.add(new_board)

    # 정답을 찾을 수 없으므로 -1 반환
    return -1


# 상하좌우 이동 위함
dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]

# 입력 값
board = ''.join([''.join(sys.stdin.readline().split()) for _ in range(3)])
# 보드판 탐색 여부
visited = set()

print(solution(board))

---

🔗 문제 링크

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

1525번: 퍼즐

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다