이번 문제는 정말 많은 시간을 고민하였다. BFS를 사용했는데, 처음에는 이해를 잘못해서 벽에 닿기 전에 방향을 틀 수 있다고 생각하고 구현하였고, 문제를 제대로 이해하고 코드를 계속해서 수정해보았지만 6%를 넘어가지 못하고 오답처리 되었다. 결국은 구글에서 코드를 찾아 보았다.

BFS를 돌며 4가지 방향에 대하여 벽에 닿거나 구멍에 빠질 때까지 계속해서 이동을 시켜야 한다. 만약 벽에 닿는다면 벽에 닿기 전까지의 좌표로 수정해주고, 파란공이 구멍에 빠지면 다음 반복을 진행해야 한다. 방향을 바꿀 때만 카운팅 변수를 증가시키며 반복하였다.

• N, M을 입력받는다.
• 보드에 해당하는 B를 입력받는다.
• 4가지 방향에 대한 dx, dy를 저장한다.
• 깊이 우선 탐색에 사용할 큐 queue를 데크로 선언한다.
• 방문 처리 리스트 visited를 4차원 리스트로 선언하고 False로 채운다.
• 초기화 함수로 사용할 pos_init()함수를 선언한다.
  -> rx, ry, bx, by를 0으로 선언한다. (빨간공과 파란공의 위치를 표시)
  -> N번 반복하는 i에 대한 for문을 돌린다.
  --> M번 반복하는 j에 대한 for문을 돌린다.
  ---> B[i][j]가 R일 경우, rx, ry를 i, j로 갱신한다.
  ---> B[i][j]가 B일 경우, bx, by를 i, j로 갱신한다.
  -> queue에 (rx, ry, bx, by)를 넣는다.
  -> visited[rx][ry][bx][by]를 True로 갱신한다.
• 공의 이동을 나타낼 함수 move를 x, y, dx, dy를 인자로 갖도록 선언한다.
  -> 카운팅 변수 cnt를 0으로 선언한다.
  -> B[x+dx][y+dy]가 #가 아니고, O가 아닐 동안 반복하는 while문을 돌린다.
  --> x에 dx를 더한다.
  --> y에 dy를 더한다.
  --> cnt를 1 증가시킨다.
  -> x, y, cnt를 반환한다.
• bfs()함수를 선언한다.
  -> pos_init()함수를 호출한다.
  -> queue가 존재하는 동안 반복하는 while문을 돌린다.
  --> rx, ry, bx, by, depth를 queue에서 추출한다.
  --> 만약 depth가 10보다 클 경우, 반복문을 탈출한다.
  --> 4번 반복하는 i에 대한 for문을 돌린다.
  ---> nrx, nry, rcnt를 move(rx, ry, dx[i], dy[i])의 반환값으로 저장한다.
  ---> nbx, nby, bcnt를 move(bx, by, dx[i], dy[i])의 반환값으로 저장한다.
  ---> 만약 B[nbx][nby]가 아닐 경우,
  ----> 만약 B[nrx][nry]가 O일 경우, depth를 출력하고 반환한다.
  ----> 만약 nrx와 nbx가 같고, nry와 nby가 같을 경우,
  -----> rcnt가 bcnt보다 클 경우,
  ------> nrx에서 dx[i]를 뺀다.
  ------> nry에서 dy[i]를 뺀다.
  -----> 그 외의 경우,
  ------> nbx에서 dx[i]를 뺀다.
  ------> nby에서 dy[i]를 뺀다.
  ----> 만약 visited[nrx][nry][nbx][nby]가 False일 경우,
  -----> visited[nrx][nry][nbx][nby]를 True로 갱신한다.
  -----> queue에 (nrx, nry, nbx, nby, depth+1)을 넣는다.
  -> -1을 출력한다. (실패의 경우)
• bfs()를 호출한다.

Code

from collections import deque
N, M = map(int, input().split())
B = [list(input().rstrip()) for _ in range(N)]
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)]
def pos_init():
    rx, ry, bx, by = 0, 0, 0, 0
    for i in range(N):
        for j in range(M):
            if B[i][j] == 'R':
                rx, ry = i, j
            elif B[i][j] == 'B':
                bx, by = i, j
    queue.append((rx, ry, bx, by, 1))
    visited[rx][ry][bx][by] = True
def move(x, y, dx, dy):
    cnt = 0
    while B[x+dx][y+dy] != '#' and B[x][y] != 'O':
        x += dx
        y += dy
        cnt += 1
    return x, y, cnt
def bfs():
    pos_init()
    while queue:
        rx, ry, bx, by, depth = queue.popleft()
        if depth > 10:
            break
        for i in range(4):
            nrx, nry, rcnt = move(rx, ry, dx[i], dy[i])
            nbx, nby, bcnt = move(bx, by, dx[i], dy[i])
            if B[nbx][nby] != 'O':
                if B[nrx][nry] == 'O':
                    print(depth)
                    return
                if nrx == nbx and nry == nby:
                    if rcnt > bcnt:
                        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))
    print(-1)
bfs()