[python] 백준 13460 구슬 탈출 2

https://www.acmicpc.net/problem/13460

13460번: 구슬 탈출 2

 

문제 해결

• 삼성 문제의 전형적인 시물레이션 문제
• 기울면 무조건 한 칸 움직이는 것이 아닌 몇 칸 움직일 수 있다는 점이 다른문제와 다르다.
• 즉 벽에 막히거나 구멍에 들어가서 상황이 종료될때까지 한 방향으로 계속 움직인다.

 

CODE

import sys
input = sys.stdin.readline
from collections import deque
def bfs(b,r):
    visited = []
    visited.append(b+r)
    que = deque()
    que.append(b+r+[0])
    while que:
        nbx, nby, nrx, nry, cnt = que.popleft()
        if cnt >10:
            return -1
        elif board[nrx][nry] == 'O':
            return cnt
        for dx, dy in zip(dxs,dys):
            mrx, mry = nrx, nry
            while True:
                mrx += dx
                mry += dy
                if board[mrx][mry] == '#':
                    mrx, mry = mrx-dx, mry-dy
                    break
                elif board[mrx][mry] == 'O': break
            mbx, mby = nbx, nby
            while True:
                mbx += dx
                mby += dy
                if board[mbx][mby] == '#':
                    mbx -= dx
                    mby -= dy
                    break
                elif board[mbx][mby] =='O':break
            if board[mbx][mby] =='O':
                continue
            if mrx==mbx and mry==mby:
                if abs(mrx-nrx)+ abs(mry-nry) > abs(mbx-nbx)+abs(mby-nby):
                    mrx -= dx
                    mry -= dy
                else:
                    mbx -= dx
                    mby -= dy
            if (mbx,mby,mrx,mry) not in visited:
                que.append([mbx,mby,mrx,mry,cnt+1])
                visited.append((mbx,mby,mrx,mry))
    return -1
if __name__=='__main__':
    n, m = map(int, input().split()) # 세로, 가로 길이
    # 움직이는 방향 위 아래 왼쪽 오른쪽
    dxs = [-1, 1, 0, 0]
    dys = [0, 0, -1, 1]
    board = [[str(c) for c in input().rstrip()] for _ in range(n)]
    for i in range(n):
        for j in range(m):
            if board[i][j] == 'B':
                blue = [i,j]
            elif board[i][j] =='R':
                red = [i,j]
    answer =  bfs(blue,red)
    print(answer)