[BOJ/백준] 15644 구슬 탈출 3

from collections import deque
def bfs(red,blue):
    stack = deque()

    stack.append((*red,*blue,0,''))
    dx = [-1,1,0,0]
    dy = [0,0,-1,1]
    direction = ['U','D','L','R']
    while stack:
        rx,ry,bx,by,dis,route = stack.popleft()

        if dis >= 10:
            return (-1,'-')

        for i in range(4):
            nrx,nry = rx,ry
            r_p = 0
            while 0<=nrx<N and 0<=nry<M and arr[nrx][nry] != '#' and arr[nrx][nry] != 'O':
                nrx += dx[i]
                nry += dy[i]
                r_p += 1
            nbx,nby = bx,by
            b_p = 0
            while 0<=nbx<N and 0<=nby<M and arr[nbx][nby] != '#' and arr[nbx][nby] != 'O':
                nbx += dx[i]
                nby += dy[i]
                b_p += 1

            if (nbx,nby) == (nrx,nry):
                if arr[nbx][nby] == 'O':
                    continue
                if r_p > b_p:
                    nrx -= dx[i]
                    nry -= dy[i]
                else:
                    nbx -= dx[i]
                    nby -= dy[i]

            elif arr[nbx][nby] == 'O':
                continue
            elif arr[nrx][nry] == 'O':
                return (dis+1,route + direction[i])
            nrx -= dx[i]
            nry -= dy[i]
            nbx -= dx[i]
            nby -= dy[i]
            if not visited[nrx][nry][nbx][nby]:continue
            visited[nrx][nry][nbx][nby] = False
            stack.append((nrx,nry,nbx,nby,dis+1,route+direction[i]))
    return (-1,'-')

N,M = map(int,input().split())


arr = []
blue = []
red = []
for x in range(N):
    temp = list(input())
    for y in range(M):
        if temp[y] == 'B':
            blue = (x,y)
        elif temp[y] == 'R':
            red = (x,y)
    arr.append(temp)


visited = [[[[True for _ in range(M)] for _ in range(N)] for _ in range(M)] for _ in range(N)]


result = bfs(red,blue)
if result[0] != -1:
    print(result[0])
    print(result[1])
else:
    print(result[0])

 

 

 이 문제는 사실상 구슬탈출 2와 동일한 문제이다.

 

 

구슬 탈출2와 달라진점은 이동방향을 저장시키는 것외에는 없다.

 

 

문제를 푸는 방식은 다음과 같다.

 

먼저 방문배열을 4차원 배열로 만들어준다.

 

그 이유는, 빨간색공이 안 움직이지만, 파란공만 움직이는 경우도 있고,

 

파란공만 움직이고, 빨간공이 움직이지 않을때가 있으므로, 구분을 하기위해 4차원 배열을 선언을 해주었다.

 

 

그리고 BFS를 하는 과정은 다음과 같다. 한 방향으로 정하고 각가 red ball과 blue ball을

 

구멍 혹은 벽을 만나기전까지 계속 굴려준다.

 

그러면 최종적으로 위치하곳은 벽 혹은 구멍일 것이다. 이 과정에서 각각의 움직이는 횟수도 세어주었다.

 

먼저 구멍에 빠졌는지 확인을 해주자.

 

파란공과 빨간공이 전부 빠졌다면, 이것은 패배한것이므로, 제외를 해주자.

 

그리고 파란공만 들어간거면 그것 또한 패배한 것이므로, 제외를 하자.

 

그리고 빨간공만 들어갔을때에는 그때는 이긴것이므로, 지금까지 누적된 이동경로를 반환을 해주면 된다.

 

그리고 두 공의 위치가 최종적으로 같다면, 둘중 먼저 해당지점에 먼저와있는지가 중요하다.

 

우리는 위에서 반복횟수를 세어주었다.

 

반복 횟수가 적다는것은 더 빨리 도착한 것이므로, 반복횟수가 많은 볼을 한칸 뒤로 빼준다.

 

이러한 작업을 다 마치고 나면 위에서 우리는 벽이나 구멍외에는 멈추지 않았다.

 

그러면 현재 볼들이 있는 위치는 벽일테니, 뒤로 한칸씩 동일하게 이동해준다.

 

이렇게 한뒤에, 우리가 방문하지 않은 곳이면 방문표시를하고 stack에 넣어주면 된다.

 

 

이 문제는 방문을 어떻게 할것인가, 그리고 공을 굴릴때 어떻게 한번에 끝까지 굴릴것인가. 그리고 같은 위치에

 

중첩됬을때 어떻게 해결하는지 중요한 문제였다.