[백준 알고리즘] 13460번 구슬 탈출2. 파이썬(python)

from collections import deque
n,m=map(int, input().split())
graph=[]

# 각 구슬의 위치를 혹인
for i in  range(n):
    graph.append(list(input()))
    for j in range(m):
        if graph[i][j] == 'R': # 빨간구슬 위치
            rx, ry = i, j
        elif graph[i][j] == 'B': # 파란구슬 위치
            bx, by = i, j

# 상 하 좌 우로 탐색
dx = [-1, 1, 0, 0]
dy = [0, 0, -1 ,1]
visited = [] # 방문여부를 판단하기 위한 리스트

def move(_x,_y,dx,dy,cnt):
    while graph[_x+dx][_y+dy] != '#' and graph[_x][_y] != 'O':
        _x+=dx
        _y+=dy
        cnt+=1
    return _x,_y,cnt

def bfs(rx, ry, bx, by):
    q=deque() # 큐 생성
    q.append((rx,ry,bx,by)) # 구슬 위치를 큐에 저장
    visited.append((rx, ry, bx, by)) # 방문여부
    cnt=0
 
    while q:
        for _ in range(len(q)):
            rx, ry, bx, by=q.popleft()
            if cnt > 10: # 움직인 횟수가 10회 초과면 -1 출력
                print(-1)
                return
            if graph[rx][ry]=='O': # 빨간 구슬이 구멍에 들어감
                print(cnt)
                return
            for i in range(4): #상하좌우 탐색
                nrx, nry, rc = move(rx, ry, dx[i], dy[i],0)
                nbx, nby, bc = move(bx, by, dx[i], dy[i],0)

                if graph[nbx][nby]=='O': # 파란구슬이 구멍에 들어가면
                    continue # 무시
                if nrx == nbx and nry == nby: # 두 구슬의 위치가 같다면 더 많이 이동한 구슬을 뒤로가기
                    if rc>bc: # 빨간 구슬이 더 많이 이동했으면
                        nrx, nry = nrx-dx[i], nry-dy[i] # 뒤로이동
                    else: # 파란 구슬이 더 많이 이동했으면
                        nbx, nby = nbx-dx[i], nby-dy[i] # 뒤로이동
                
                if (nrx, nry, nbx, nby) not in visited: # 이동한 위치가 방문한 적이 없으면 
                    q.append((nrx, nry, nbx, nby)) # 큐에 추가
                    visited.append((nrx, nry, nbx, nby)) # 방문여부에 추가
        cnt+=1
    print(-1)
    
bfs(rx, ry, bx, by)