13460번. 구슬 탈출 2

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

 

 

0. 이것 때문에 엄청 헤맸다!! 기울이는 동작을 그만하는 것은 더 이상 구슬이 움직이지 않을 때 까지이다. 를 주의하자. 나는 이 말을 처음에 '동서남북 등으로 기울이는 행동, 즉 이 게임을 그만두는 것은 구슬이 움직이지 않을 때까지(하지만 지금생각해보니 구슬이 움직이지 않을리가 없지 않은가...)'로 이해했는데, 그게 아니라 '구슬이 한번 이동하기 시작했으면 움직이지 않을 때까지 계속 이동한다'로 이해해야 한다.

 

1. 실제 게임하는 것처럼 살살 움직이면 중간에도 다른 방향(밑으로라던지...)으로 빠질 수 있다고 생각한게 잘못이었다. 하지만 이 게임에서 중력은 없다.

 

2. 방문 체크는 RED와 BLUE 따로 해 주는 것이 아니라 '동시에' 해야 한다. 빨간 공과 파란 공 둘다 방문했던 지점이어야만 한번 갔던 지점이라고 인식하고 가지 말아야 한다. 그래서 4차원 배열을 사용했다. 처음에는 4차원 배열이 직관적이지 않은 것 같아서 RED와 BLUE 각각의 2차원 배열로 체크했는데, 2차원 배열 2개와 4차원 배열 1개는 엄연히 다른 것이었다. 2차원 배열 두 개를 사용하면 독립 사건이 되는데, 4차원 배열 1개를 사용하면 조건부 확률이 된다고 해야 할까..

예를 들어 어떤 시점에서 red = [1, 1], blue = [2, 2] 였고, 그 다음에는 red = [3, 3], blue = [4, 4] 이었다고 해보자. 만약 이것을 4차원 배열로 방문 체크를 하면 visit[1][1][2][2] = 1, visit[3][3][4][4] = 1 일 것이다.

하지만 이것을 2차원 배열로 각각 체크를 하면

visit_red[1][1] = 1, visit_blue[2][2] = 1, visit_red[3][3] = 1, visit_blue[4][4] =1 이 되며 이것을 다시 4차원 배열로 바꿔보면

visit[1][1][2][2] = 1

visit[3][3][4][4] = 1

visit[1][1][4][4] = 1  <= 방문하지 않았는데

visit[3][3][2][2] = 1  <= 방문 체크가 되어버림

로 네 가지나 나오게 되어 버리며 이로 인해 방문하지 않은 지점도 방문했다고 인식하고 가지 않게 된다.

 

2. 방문 체크는 여느 bfs와 마찬가지로 '큐에 넣을 때' 해야 한다. 이 말은 구슬이 한 번 쭉 이동하고 난 후 멈춰선 지점이 큐에 들어간다는 뜻이 된다. 이동하는 과정에서 모든 칸이 방문 체크가 되어 버리면 안 된다. 이리저리 움직이다보면 이전에 갔던 길을 또 갈 수는 있다. 또한 move 함수 자체는 이동을 '해 보는' 함수이므로, 이동을 '해 보는' 도중에 방문 체크를 해서도 안 된다. 이동하고 나니 RED와 BLUE가 같은 곳에 있어서 이동해줘야 하는 경우였을 수도 있기 때문이다. 아니면 BLUE가 구멍에 빠졌을 수도 있고...일단 이동을 해보고 유효한 움직임이고 도착 지점이 방문한 적이 없는 지점이면 그 때 이것을 유효한 움직임이었다고 인정하고 그 다음 이동을 위해서 큐에 넣는 것이다.

 

3. 기울임 횟수(tilt_count) 는 큐에 넣어서 기록해야 한다. 그래야 한 번 while 문을 돌면서 동서남북으로 이동할 때 같은 tilt_count를 가지고 큐에 추가될 수 있다. while문이든 for문이든 반복문 아래에 직접 tilt_count를 세면 안 된다. 

 

import sys
import collections


def move(x, y, dx, dy):
    count = 0
    while board[x+dx][y+dy] != '#' and board[x][y] != 'O':
        x += dx
        y += dy
        count += 1
    return x, y, count


def bfs():
    queue = collections.deque()
    queue.append(red_first+blue_first+[1])
    visited[red_first[0]][red_first[1]][blue_first[0]][blue_first[1]] = 1
    x = [1, -1, 0, 0]
    y = [0, 0, 1, -1]

    while queue:
        rx, ry, bx, by, tilt_count = queue.popleft()

        if tilt_count > 10:
            return -1

        for d in range(4):
            next_rx, next_ry, r_count = move(rx, ry, x[d], y[d])  # 기울여서 이동했을 때 [끝지점의 x 좌표, y 좌표, 이동한 칸수]
            next_bx, next_by, b_count = move(bx, by, x[d], y[d])

            if board[next_bx][next_by] == 'O':  # blue가 구멍에 빠졌다면 해당 기울임(움직임) 무시
                continue
            if board[next_rx][next_ry] == 'O':
                return tilt_count

            # red와 blue가 같을 경우 이동 칸수가 많은 것(더 멀리서 온 것)을 한 칸 뒤로 빼줌
            if next_rx == next_bx and next_ry == next_by:
                if r_count > b_count:
                    next_rx -= x[d]
                    next_ry -= y[d]
                else:
                    next_bx -= x[d]
                    next_by -= y[d]

            # 각 기울임에 따라 도착하는 지점만을 visit 체크한다
            # 단 둘 중에 하나라도 방문하지 않은 지점이라면 가능한 기울임이라는 뜻이다
            if not visited[next_rx][next_ry][next_bx][next_by]:
                visited[next_rx][next_ry][next_bx][next_by] = 1
                queue.append([next_rx, next_ry, next_bx, next_by, tilt_count+1])


if __name__ == '__main__':
    n, m = map(int, sys.stdin.readline().split())
    board, red_first, blue_first = [], [], []
    visited = [[[[0 for _ in range(m)] for _ in range(n)] for _ in range(m)] for _ in range(n)]
    for i in range(n):
        tmp = sys.stdin.readline().rstrip()
        if 'R' in tmp:
            red_first = [i, tmp.index('R')]
        if 'B' in tmp:
            blue_first = [i, tmp.index('B')]
        board.append(tmp)

    print(bfs())