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

input :

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

output :

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

• 둘째 줄에 어떻게 기울여야 하는지 순서대로 출력

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

조건 :

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

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

• 공은 동시에 움직인다.

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

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

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

---

BOJ 13460 구슬 탈출 2에서 바껴야 하는 부분은 어떻게 기울였는지를 기록해야 한다.

다음 풀이

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

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

dx, dy 벡터를 움직일 방식을 저장해 둬야 한다. y방향이 "오른", "왼"쪽이고 x방향이 "위", "아래"이다.

이 방향이 헷갈려서 처음에 답이 이상하게 나왔다.

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, ""))

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

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

        if len(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(len(d) + 1)
                print(d + way[i])
                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 + way[i]))

    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]
way = ["R", "L", "D", "U"]

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)