https://www.acmicpc.net/problem/13460
시간 2초, 메모리 512MB

input :

• N M (3 ≤ N, M ≤ 10)
• '.', '#', 'O', 'R', 'B'로 이루어진 지도

output :

• 최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 출력

• 10번 이하로 움직여서 빨간 구슬을 구멍을 통해 빼낼 수 없으면 -1을 출력

조건 :

• 입력되는 모든 보드의 가장자리에는 모두 '#'이 있다. 구멍의 개수는 한 개 이며, 빨간 구슬과 파란 구슬은 항상 1개가 주어진다.

• 왼쪽으로 기울이기, 오른쪽으로 기울이기, 위쪽으로 기울이기, 아래쪽으로 기울이기와 같은 네 가지 동작이 가능

• 공은 동시에 움직인다.

• 빨간 구슬이 구멍에 빠지면 성공이지만, 파란 구슬이 구멍에 빠지면 실패이다.

• 빨간 구슬과 파란 구슬이 동시에 구멍에 빠져도 실패

• 빨간 구슬과 파란 구슬은 동시에 같은 칸에 있을 수 없다

BOJ 13459 구슬 탈출에서 바껴야 하는 부분은 마지막 출력할 때 몇 번 움직였는지를 보면 된다.

다음 풀이

1. 중력에 의한 이동
2. 구멍에 동시에 빠진 경우
3. 이동의 순서

중력에 의한 움직임이기 때문에 특정 방향으로 계속 이동을 하다가 "벽"을 만날때, "구멍"에 위치할 때 멈춰야 한다.
동시에 구멍에 들어가는 경우를 조건으로 걸어야 한다.
"R", "B"가 움직일 때 둘이 동일한 위치에 있는데 이동 거리가 다른 것으로 확인할 수 있다.
추가적으로 다음 위치에 벽이 있으면 멈추지만, 현재 위치가 구멍이어도 멈춘다.
이를 위해 dx, dy를 해서 체킹을 해야 한다.

추가적으로 BFS를 수행하면서 횟수를 기록하기 위한 변수를 하나 추가한다.

import sys
from collections import deque

def move (x, y, i):
    # i == direction
    cnt = 0
    while graph[x + dx[i]][y + dy[i]] != "#" and graph[x][y] != "O":
        x += dx[i]
        y += dy[i]
        cnt += 1

    return x, y, cnt

def bfs(rx, ry, bx, by):
    q = deque([])
    q.append((rx, ry, bx, by, 0))

    visit = dict()
    visit[(rx, ry, bx, by)] = 1

    while q:
        rx, ry, bx, by, d = q.popleft()

        if d >= 10:
            break

        for i in range(4):
            temp_rx, temp_ry, temp_rcnt = move(rx, ry, i)
            temp_bx, temp_by, temp_bcnt = move(bx, by, i)

            # 동시에 구멍에 들어갈 수 있는 경우를 찾기 위함.
            if graph[temp_bx][temp_by] == "O":
                continue

            if graph[temp_rx][temp_ry] == "O":
                print(d + 1)
                return

            # 위치가 동일한 경우에.
            # 더 많이 이동한 좌표가 다른 구슬을 무시하고 지나간것이 됨
            if temp_rx == temp_bx and temp_ry == temp_by:
                if temp_rcnt > temp_bcnt:
                    temp_rx, temp_ry = temp_rx - dx[i], temp_ry - dy[i]
                else:
                    temp_bx, temp_by = temp_bx - dx[i], temp_by - dy[i]

            if (temp_rx, temp_ry, temp_bx, temp_by) not in visit:
                visit[(temp_rx, temp_ry, temp_bx, temp_by)] = 1
                q.append((temp_rx, temp_ry, temp_bx, temp_by, d + 1))

    print(-1)


n, m = map(int, sys.stdin.readline().split())
graph, rx, ry, bx, by = [], 0, 0, 0, 0
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

for x in range(n):
    temp = list(sys.stdin.readline().rstrip())
    graph.append(temp)

    for y in range(m):
        if temp[y] == "R":
            rx, ry = x, y
        if temp[y] == "B":
            bx, by = x, y

bfs(rx, ry, bx, by)