백준 13459 구슬 탈출

bfs를 응용하는 문제이다.

bfs를 통해 최단거리의 목표지점을 찾는데, 기존의 문제들은 target을 목표지점가지 한 칸 씩 이동하여서 목표물을 찾았다.
그러나 한칸씩 이동하는 것이 아니라 몇칸씩 이동할지 제안을 주면서 bfs를 사용하면 이 문제를 해결할 수 있다.

move함수를 통해 벽바로 전까지 가거나 홀을 발견한 경우까지 탐색한다.
이 이동한 칸에 대해 4중 배열의 visited를 만들고 방문처리를 해준다.
빨간공, 파란공 각각 한칸을 차지하기 때문에 더 많이 움직이 공에 대하여 움직인 방향 반대로 한칸 빼주어야 한다.

from collections import deque
n,m = list(map(int,input().split()))
board = []
for i in range(n):
    tmp = list(input())
    board.append(tmp)
for i in range(n):
    for j in range(m):
        if board[i][j] == 'R':
            red = (i,j)
        elif board[i][j] == 'B':
            blue = (i,j)

## d = 0부터 위왼아오
dx = [-1,0,1,0]
dy = [0,1,0,-1]
visited= [[[[0]*m for i in range(n)] for i in range(m)] for i in range(n)]
def move(x,y, direction):
    cnt = 0
    while board[x+dx[direction]][y + dy[direction]] != '#' and board[x][y] != 'O':
        x += dx[direction]
        y += dy[direction]
        cnt += 1
    return x,y,cnt

def bfs():
    q = deque([])
    q.append((red[0],red[1],blue[0],blue[1],0))
    while q:
        rx,ry,bx,by,cnt = q.popleft()
        if cnt >= 10:
            break
        for i in range(4):
            nrx,nry,red_cnt = move(rx,ry,i)
            nbx,nby,blue_cnt = move(bx,by,i)
            if board[nbx][nby] == 'O':
                continue
            if board[nrx][nry] == 'O':
                return 1
            if nrx == nbx and nry == nby:  ## 두점 같으면
                if red_cnt > blue_cnt:
                    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] = 1
                q.append((nrx,nry,nbx,nby,cnt + 1))
    return 0

print(bfs())