백준 15653 구슬탈출4

from collections import deque

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

n, m = map(int, input().split())
g = [list(input()) for _ in range(n)]

for i in range(n):
    for j in range(m):
        if g[i][j] == 'R':
            frx, fry = i, j
        elif g[i][j] == 'B':
            fbx, fby = i, j

rcheck = [[-1] * m for _ in range(n)]
bcheck = [[-1] * m for _ in range(n)]
redout = False
blueout = False

q = deque()
q.append((frx, fry, fbx, fby))
rcheck[frx][fry] = 0
bcheck[fbx][fby] = 0

while q:
    rx, ry, bx, by = q.popleft()
    for i in range(4):
        # 빨간 구슬 이동 # 구멍에 빠졌다면 그만
        nrx, nry = rx, ry
        while True:
            nrx, nry = nrx + dx[i], nry + dy[i]
            if g[nrx][nry] == '#':
                nrx -= dx[i]
                nry -= dy[i]
                break
            if g[nrx][nry] == 'O':
                rcheck[nrx][nry] = rcheck[rx][ry] + 1
                redout = True
                break

        # 파란 구슬 이동 # 구멍에 빠졌다면 그만
        nbx, nby = bx, by
        while True:
            nbx, nby = nbx + dx[i], nby + dy[i]
            if g[nbx][nby] == '#':
                nbx -= dx[i]
                nby -= dy[i]
                break
            if g[nbx][nby] == 'O':
                blueout = True
                break

        if blueout == True:
            continue

        if redout == True:
            break

        # 같은 곳에서 만난다면 순서 정해주기
        if nrx == nbx and nry == nby:
            # 빨간 구슬이 더 가까웠으면
            if abs(nrx-rx) + abs(nry-ry) <  abs(nrx-bx) + abs(nry-by):
                # 파란구슬 하나 물러줌
                nbx -= dx[i]
                nby -= dy[i]
            else:
                nrx -= dx[i]
                nry -= dy[i]

        if rcheck[nrx][nry] == -1:
            rcheck[nrx][nry] = rcheck[rx][ry] + 1
            bcheck[nbx][nby] = 0
            q.append((nrx, nry, nbx, nby))
    
    if redout == True:
        print(rcheck[nrx][nry])
        break  

맨처음 : 파란 구슬과 빨간 구슬을 따로 따로 check 배열을 만듬 -> 경우의 수 따지기가 어려움
6 7
#######
#RBO.##
#..##.#
#.....#
#.###.#
#######
ANS: 4
게시판의 반례 이거 넣어보면 틀림

from collections import deque

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

n, m = map(int, input().split())
g = [list(input()) for _ in range(n)]

for i in range(n):
    for j in range(m):
        if g[i][j] == 'R':
            frx, fry = i, j
        elif g[i][j] == 'B':
            fbx, fby = i, j
check = [[[[-1]*m for _ in range(n)] for _ in range(m)] for _ in range(n)]
out = False
twoout = False
q = deque()
q.append((frx, fry, fbx, fby))
check[frx][fry][fbx][fby] = 0

while q:
    rx, ry, bx, by = q.popleft()
    for i in range(4):
        # 빨간 구슬 이동 # 구멍에 빠졌다면 그만
        nrx, nry = rx, ry
        while True:
            nrx, nry = nrx + dx[i], nry + dy[i]
            if g[nrx][nry] == '#':
                nrx -= dx[i]
                nry -= dy[i]
                break
            if g[nrx][nry] == 'O':
                break

        # 파란 구슬 이동 # 구멍에 빠졌다면 그만
        nbx, nby = bx, by
        while True:
            nbx, nby = nbx + dx[i], nby + dy[i]
            if g[nbx][nby] == '#':
                nbx -= dx[i]
                nby -= dy[i]
                break
            if g[nbx][nby] == 'O':
                break
        if g[nbx][nby] == 'O' and g[nrx][nry] == 'O':
            twoout = True
            break
        # 같은 곳에서 만난다면 순서 정해주기
        if nrx == nbx and nry == nby:
            # 빨간 구슬이 더 가까웠으면
            if abs(nrx-rx) + abs(nry-ry) <  abs(nbx-bx) + abs(nby-by):
                # 파란구슬 하나 물러줌
                nbx -= dx[i]
                nby -= dy[i]
            else:
                nrx -= dx[i]
                nry -= dy[i]

        if g[nbx][nby] == 'O':
            continue

        if g[nrx][nry] == 'O':
            out = True
            check[nrx][nry][nbx][nby] = check[rx][ry][bx][by] + 1
            break

        
        
        if check[nrx][nry][nbx][nby] == -1:
            check[nrx][nry][nbx][nby] = check[rx][ry][bx][by] + 1
            q.append((nrx, nry, nbx, nby))

    if out == True:
        break

if out == True:
    print(check[nrx][nry][nbx][nby])
elif twoout == True:
    print(-1)
else:
    print(-1)  

구멍으로 동시에 두 구슬이 들어가는 경우 종료되는 것도 고침
다시 게시판에서 찾은 반례
6 6
######/
#R#BO#
#....#
###..#
#.#..#
######/
answer: 6
이 반례가 또 안됨
여러번 굴려서 동시에 들어가는 것을 피할 수 있다