백준 구슬 탈출 2 [13460] Python 코드 + 해설

문제 설명

구슬 탈출은 빨간 구슬을 구멍에 넣는 것이 목표인 게임이다. 직사각형 보드에 빨간 구슬과 파란 구슬이 각각 하나씩 놓여 있으며, 보드를 기울여 구슬들을 움직일 수 있다. 중요한 점은 파란 구슬은 구멍에 들어가면 안 되고, 빨간 구슬만 구멍에 빠져야 한다.
보드를 왼쪽, 오른쪽, 위, 아래로 기울일 수 있으며, 한 번 기울일 때마다 구슬들은 그 방향으로 모두 이동할 수 있을 만큼 이동한다. 두 구슬은 동시에 움직이며, 이동 중에 서로 겹칠 수 없다.
목표는 최소 횟수로 빨간 구슬을 구멍에 넣는 것이다. 단, 이동 횟수는 10번을 초과할 수 없다. 그렇다면 어떻게 이 문제를 해결할 수 있을까?

해결 방법: BFS를 활용한 상태 탐색

이 문제는 구슬들의 모든 가능한 상태를 탐색하여 최소 횟수로 빨간 구슬을 구멍에 넣는 경로를 찾는 것이다. 여기서 BFS(너비 우선 탐색) 알고리즘을 사용하면 최단 경로를 효율적으로 찾을 수 있다.

BFS란?

BFS는 그래프 탐색 알고리즘 중 하나로, 시작 노드에서부터 인접한 노드를 모두 방문한 후, 그 다음 레벨의 노드들을 방문하는 방식이다. 이 방법을 사용하면 최단 경로를 보장할 수 있어 이 문제에 적합하다.

bfs

구체적인 해결 단계

1. 입력 처리 및 초기 상태 설정
   • 보드를 입력받고, 빨간 구슬(R), 파란 구슬(B), 구멍(O)의 위치를 파악한다.
   • 구슬들의 위치를 저장하고, 보드에서 구슬을 제거하여 이동 시 간섭을 피한다.
2. 구슬 이동 함수 구현
   • 네 가지 방향(상, 하, 좌, 우)에 대해 구슬을 이동시키는 함수를 작성한다.
   • 구슬은 벽(#)이나 구멍(O)을 만나기 전까지 이동한다.
   • 이동 중 구멍에 빠지면 해당 정보를 반환한다.
   • 두 구슬이 같은 위치에 도달하면 이동 거리를 비교하여 뒤에 온 구슬을 한 칸 뒤로 이동시킨다.
3. BFS를 통한 상태 탐색
   • 큐(queue)를 사용하여 BFS를 구현한다.
   • 초기 상태(빨간 구슬 위치, 파란 구슬 위치, 이동 횟수)를 큐에 넣는다.
   • 방문한 상태를 기록하기 위해 4차원 배열을 사용한다: visited[빨간X][빨간Y][파란X][파란Y]
   • 큐에서 상태를 하나씩 꺼내 네 방향으로 구슬을 이동시키고 새로운 상태를 생성한다.
   • 이동 횟수가 10을 초과하면 실패로 간주한다.
   • 파란 구슬이 구멍에 빠지면 해당 상태는 무시한다.
   • 빨간 구슬이 구멍에 빠지면 현재 이동 횟수를 반환한다.
4. 결과 출력
   • BFS 탐색 중 빨간 구슬을 구멍에 넣는 경우를 찾으면 그때의 이동 횟수를 출력한다.
   • 10번 이내에 해결하지 못하면 -1을 출력한다.

from collections import deque

# 이동 방향 설정: 상, 하, 좌, 우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def move(x, y, dx, dy, board):
    count = 0
    # 다음 위치가 벽이 아니고 구멍이 아닐 때까지 이동한다.
    while board[x + dx][y + dy] != '#' and board[x][y] != 'O':
        x += dx
        y += dy
        count += 1
        if board[x][y] == 'O':
            break
    return x, y, count

def bfs(board, rx, ry, bx, by):
    n, m = len(board), len(board[0])
    visited = [[[[False]*m for _ in range(n)] for _ in range(m)] for _ in range(n)]
    queue = deque()
    queue.append((rx, ry, bx, by, 0))
    visited[rx][ry][bx][by] = True

    while queue:
        rx, ry, bx, by, depth = queue.popleft()
        if depth >= 10:
            return -1
        for i in range(4):
            nrx, nry, rc = move(rx, ry, dx[i], dy[i], board)
            nbx, nby, bc = move(bx, by, dx[i], dy[i], board)

            # 파란 구슬이 구멍에 빠진 경우
            if board[nbx][nby] == 'O':
                continue
            # 빨간 구슬이 구멍에 빠진 경우 성공
            if board[nrx][nry] == 'O':
                return depth + 1

            # 두 구슬이 같은 위치에 있는 경우 처리
            if nrx == nbx and nry == nby:
                if rc > bc:
                    nrx -= dx[i]
                    nry -= dy[i]
                else:
                    nbx -= dx[i]
                    nby -= dy[i]

            if not visited[nrx][nry][nbx][nby]:
                visited[nrx][nry][nbx][nby] = True
                queue.append((nrx, nry, nbx, nby, depth + 1))
    return -1

def main():
    N, M = map(int, input().split())
    board = [list(input()) for _ in range(N)]
    rx = ry = bx = by = 0
    for i in range(N):
        for j in range(M):
            if board[i][j] == 'R':
                rx, ry = i, j
                board[i][j] = '.'
            elif board[i][j] == 'B':
                bx, by = i, j
                board[i][j] = '.'
    result = bfs(board, rx, ry, bx, by)
    print(result)

if __name__ == '__main__':
    main()