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

input :

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

output :

• 파란 구슬을 구멍에 넣지 않으면서 빨간 구슬을 10번 이하로 움직여서 빼낼 수 있으면 "1"을 없으면 "0"을 출력

조건 :

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

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

• 공은 동시에 움직인다.

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

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

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

---

알고리즘 기말고사에 나온 문제로 제대로 풀지 못했던 문제이다. 그 때는 a_star처럼 보여서 a_star로 대충 때려 맞춰서 부분점수를 얻었다.

따져야 하는 부분이 3가지? 정도 있다.
1. 움직이는 방법
2. 같은 위치에 존재
3. 파란 공이 동시에 구멍에 빠짐

다음 풀이

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

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


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)