[백준] 구슬 탈출 2.py

import sys
import math

n, m = map(int, sys.stdin.readline().split())
maps = []
for y in range(n):
    arr = list(sys.stdin.readline())
    maps.append(arr)
    for x in range(len(arr)):
        if arr[x] == 'R':
            r = (y, x)
            # 맵을 재활용하기 위해 처음 위치값만 저장한 뒤 값을 .로 바꿔준다
            arr[x] = '.'
        if arr[x] == 'B':
            b = (y, x)
            arr[x] = '.'
    
mins = math.inf   

def bfs(maps, start_r, start_b, dirs, cnt):
    global mins
    if cnt > 10:
        return
    # 어디로 이동할 건지 direction
    dy, dx = dirs
    
    # 각 구슬의 y좌표, x좌표
    ry, rx = start_r 
    by, bx = start_b
    
    # 정지하기까지 이동한 횟수. 같은 위치에 있을 때 선후관계를 가리는 용도
    r_cnt, b_cnt = 0, 0
    
    # 구슬이 빠져나갔는지 여부
    r_out, b_out = False, False
    
    # 빨간 공
    ny, nx = ry + dy, rx + dx
    while 0 <= ny < len(maps) and 0 <= nx < len(maps[0]):
        r_cnt += 1
        # 구슬이 밖으로 빠져나옴
        if maps[ny][nx] == 'O':
            r_out = True
            break
        # 움직일 수 없음
        elif maps[ny][nx] == '#':
            start_r = (ry, rx)
            r_cnt -= 1
            break
        # 이동 가능
        elif maps[ny][nx] == '.':
            ry, rx = ny, nx
            ny, nx = ry + dy, rx + dx
    # 파란 공
    ny, nx = by + dy, bx + dx
    while 0 <= ny < len(maps) and 0 <= nx < len(maps[0]):
        b_cnt += 1
        if maps[ny][nx] == 'O':
            b_out = True
            break
        elif maps[ny][nx] == '#':
            start_b = (by, bx)
            b_cnt -= 1
            break
        elif maps[ny][nx] == '.':
            by, bx = ny, nx
            ny, nx = by + dy, bx + dx
    
    # 두 개가 같은 위치에 겹친 경우
    if start_r == start_b:
        # r이 더 오래 걸렸으면 r을 한 칸 뒤로
        if r_cnt > b_cnt:
            start_r = (ry - dy, rx - dx)
        # b가 더 오래 걸렸으면 b를 한 칸 뒤로
        else:
            start_b = (by - dy, bx - dx)
    
    
    
    # b가 통과한 경우 실패
    if b_out:
        return
    # r만 통과하고 b는 통과하지 못한 경우 성공
    elif r_out and not b_out:
        mins = min(mins, cnt)
        return
    ## 둘 다 전혀 움직이지 않은 경우 실패
    elif r_cnt == b_cnt == 0:
        return
    else:
        bfs(maps, start_r, start_b, (0, 1), cnt + 1)
        bfs(maps, start_r, start_b, (1, 0), cnt + 1)
        bfs(maps, start_r, start_b, (0, -1), cnt + 1)
        bfs(maps, start_r, start_b, (-1, 0), cnt + 1)
        
dirs = [(0,1), (0,-1), (1, 0), (-1,0)]
for head in dirs:
    bfs(maps, r, b, head, 1)

if mins == math.inf:
    print(-1)
else:
    print(mins)