[BOJ] 13460. 구슬 탈출2 (🔮, 구현/시뮬레이션/그래프 탐색)

🔗

풀이

모든 가능성을 고려하면서 최소 횟수를 구하는 문제이므로 그래프 탐색의 너비 우선 탐색 방식과 구슬의 이동 경로를 시뮬레이션하는 두 가지 방식을 합해서 풀이했다.

우선 빨간 구슬과 파란 구슬은 사방으로 움직일 수 있고, 벽을 마주하거나 다른 구슬을 만나기 전까지는 계속 움직이게 된다. 그래서 벽을 마주하거나 다른 구슬을 마주칠 때까지 계속 움직이다가 해당 조건에 걸리게 되면 직전 위치까지만 이동하는 것으로 계산했다.

어떤 구슬이든 구멍에 들어가게 되면 좌표 상에는 위치가 존재하지 않게 된다. 이때는 (-1, -1)로 위치를 변경했다. 만약 두 구슬의 좌표가 해당 좌표값이라면 구멍 안으로 들어가게 된 것으로 판단했다.

두 구슬의 위치 좌표값을 키 값으로 방문처리를 했다. 두 구슬의 위치와 똑같은 위치에 다시 위치하게 된다면 결국 한 번 방문했던 곳이 되므로, 두 구슬의 위치값과 똑같은 값이 또 나와서 또 방문하게 하는 일은 없게 했다.

빨간 구슬만 구멍에 들어가는 경우 카운트 값을 출력했다. 이때 파란 구슬도 구멍에 들어가게 된다면 해당 경우는 그냥 넘어갔다.

반례

7 8
########
#.#O.#R#
#....#B#
#.#....#
#......#
#......#
########

answer : 9

# 구슬 탈출

def move(this_x, this_y, other_x, other_y, d, is_red):
    global is_blue_in_hole, is_red_in_hole

    while True: 
        next_x = this_x + direction[d][0]
        next_y = this_y + direction[d][1]
        if board[next_x][next_y] == "#" or (next_x == other_x and next_y == other_y):
            return this_x, this_y
        elif board[next_x][next_y] == "O":
            if is_red:
                is_red_in_hole = True
            else:
                is_blue_in_hole = True
            return (-1, -1)
        
        this_x = next_x
        this_y = next_y

def up(R, B):
    if R[0] <= B[0]:
        R = move(*R, *B, 0, True)
        B = move(*B, *R, 0, False)
    else:
        B = move(*B, *R, 0, False)
        R = move(*R, *B, 0, True)
    return R, B

def down(R, B):
    if R[0] >= B[0]:
        R = move(*R, *B, 1, True)
        B = move(*B, *R, 1, False)
    else:
        B = move(*B, *R, 1, False)
        R = move(*R, *B, 1, True)
    return R, B

def right(R, B):
    if R[1] >= B[1]:
        R = move(*R, *B, 2, True)
        B = move(*B, *R, 2, False)
    else:
        B = move(*B, *R, 2, False)
        R = move(*R, *B, 2, True)
    return R, B

def left(R, B):
    if R[1] <= B[1]:
        R = move(*R, *B, 3, True)
        B = move(*B, *R, 3, False)
    else:
        B = move(*B, *R, 3, False)
        R = move(*R, *B, 3, True)
    return R, B

N, M = map(int, input().split())
board = [list(input()) for _ in range(N)]
direction = ((-1, 0), (1, 0), (0, 1), (0, -1))

for i in range(N):
    for j in range(M):
        if board[i][j] == "R":
            R = (i, j)
            board[i][j] = "."
        elif board[i][j] == "B":
            B = (i, j)
            board[i][j] = "."

is_red_in_hole = False
is_blue_in_hole = False

def sol(R, B):
    move_fn = {
        0: (lambda x: up(x[0], x[1])),
        1: (lambda x: down(x[0], x[1])),
        2: (lambda x: right(x[0], x[1])),
        3: (lambda x: left(x[0], x[1]))
    }
    visited = {(R, B): True}
    queue = [(R, B, 0)]
    while queue:
        R, B, cnt = queue.pop(0)
        # print(R, B, cnt)
        if cnt >= 10:
            return -1

        for k in range(4):
            new_R, new_B = move_fn[k]((R, B))

            if not visited.get((new_R, new_B)):
                visited[(new_R, new_B)] = True
                queue.append((new_R, new_B, cnt+1))

            if new_R == (-1, -1) and new_B != (-1, -1):
                return cnt + 1
    
    return -1

print(sol(R, B))