본문 바로가기
Python/백준

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

by Guardy 2024. 10. 21.
728x90
반응형

문제 설명

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

 

728x90
반응형