구슬 탈출

문제 파악

주어진 보드에서 빨간 구슬과 파란 구슬을 굴려서 빨간 구슬만 구멍에 넣을 수 있는지 확인하는 문제이다. 구슬은 상하좌우로 기울여서 굴릴 수 있으며, 빨간 구슬은 구멍에 빠지면 성공이고, 파란 구슬이 빠지면 실패로 간주한다. 최대 10번의 시도안에 빨간 구슬만 구멍에 들어가는지 확인해야 한다.

13459번: 구슬 탈출

접근 방법

1. 빨간 구슬과 파란 구슬의 초기 위치를 파악한다.
2. 네 방향으로 구슬을 굴려가면서 구슬의 이동을 시뮬레이션 한다.
   • 구슬이 이동하는 동안 벽에 부딪히거나 다른 구슬과 겹치는 등의 상황을 처리
3. 빨간 구슬만 구멍에 빠지면 성공, 최대 10번안에 성공여부 반환

코드 구현

from collections import deque

N, M = map(int, input().split())
board = [list(input().rstrip()) for _ in range(N)]


def move(x, y, dx, dy):
    cnt = 0
    while board[x + dx][y + dy] != '#' and board[x][y] != 'O':
        x += dx
        y += dy
        cnt += 1
    return x, y, cnt


def solve(N, M):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    queue = deque()
    visited = [[[[False] * M for _ in range(N)] for _ in range(M)] for _ in range(N)]

    rx, ry, bx, by = 0, 0, 0, 0
    for i in range(N):
        for j in range(M):
            if board[i][j] == 'R':
                rx, ry = i, j
            elif board[i][j] == 'B':
                bx, by = i, j

    queue.append((rx, ry, bx, by, 1))
    visited[rx][ry][bx][by] = True

    while queue:
        rx, ry, bx, by, depth = queue.popleft()
        if depth > 10:
            return False

        for i in range(4):
            nrx, nry, r_cnt = move(rx, ry, dx[i], dy[i])
            nbx, nby, b_cnt = move(bx, by, dx[i], dy[i])

            if board[nbx][nby] != 'O':
                if board[nrx][nry] == 'O':
                    return True
                if nrx == nbx and nry == nby:
                    if r_cnt > b_cnt:
                        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 False


if solve(N, M):
    print(1)
else:
    print(0)