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

input :

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

output :

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

• 빨간 구슬을 구멍을 통해 빼낼 수 없으면 -1을 출력

조건 :

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

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

• 공은 동시에 움직인다.

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

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

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

---

BOJ 13459 구슬 탈출에서 바껴야 하는 부분은 BFS 내부의 조건문만 없어지면 된다.
visit을 통해 다 확인했는지를 볼 수 있기 때문이다.

다음 풀이

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

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

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()

        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)