백준: 13459 구슬 탈출

문제

13459번: 구슬 탈출

 

문제 풀이

 기존의 그래프 문제들은 상, 하, 좌, 우로 탐색하여 하나의 목표에 대해 이동 가능한지 판단하는 문제들이었다. 하지만 이 문제는 2개의 구슬들이 기울기에 따라 상, 하, 좌, 우로 동시에 이동하는 경우에 빨간 구슬부터 먼저 탈출 가능한지를 판단하는 문제이다. 또한, 시도 횟수 10회를 초과하지 않고 탈출할 수 있어야 한다.

 

 다른 그래프 문제들은 한 번에 한 칸씩 상, 하, 좌, 우로 이동 가능한지 파악하였지만 이 문제에서는 기울기에 따라 구슬이 끝까지 굴러가게 되므로, 벽을 만나기 전까지 계속해서 이동할 수 있다는 차이점이 있다. 또한, 경우의 수 중에 파란 구슬이 먼저 탈출하는 경우는 제외하여야 한다.

 

코드

from sys import stdin
from collections import deque


def move_beads(loc, dx, dy):
    cnt = 0
    while graph[loc[X] + dx][loc[Y] + dy] != '#':
        if graph[loc[X]][loc[Y]] == 'O':
            break
        loc = [loc[X] + dx, loc[Y] + dy]
        cnt += 1
    return loc, cnt


def bfs(start):
    q = deque([start])
    dirs = ((-1, 0), (1, 0), (0, 1), (0, -1))

    while q:
        red, blue, cnt = q.popleft()

        if cnt > 10:
            break

        for dx, dy in dirs:
            next_red, red_cnt = move_beads(red, dx, dy)
            next_blue, blue_cnt = move_beads(blue, dx, dy)
            # 파란색 구슬이 먼저 탈출하는 경우의 수 제외.
            if graph[next_blue[X]][next_blue[Y]] == 'O':
                continue
            # 빨간 구슬이 먼저 탈출 가능한 경우
            if graph[next_red[X]][next_red[Y]] == 'O':
                return 1

            if next_red == next_blue:
                if red_cnt > blue_cnt:
                    next_red = [next_red[X] - dx, next_red[Y] - dy]
                else:
                    next_blue = [next_blue[X] - dx, next_blue[Y] - dy]

            r_x, r_y = next_red; b_x, b_y = next_blue

            if not visited[r_x][r_y][b_x][b_y]:
                visited[r_x][r_y][b_x][b_y] = True
                q.append([[r_x, r_y], [b_x, b_y], cnt + 1])

    return 0


if __name__ == '__main__':
    X, Y = 0, 1
    n, m = map(int, stdin.readline().split())
    graph = []
    red = blue = None
    for i in range(n):
        graph.append(list(stdin.readline().strip()))
        if red is None and 'R' in graph[i]:
            red = [i, graph[i].index('R')]
        if blue is None and 'B' in graph[i]:
            blue = [i, graph[i].index('B')]

    visited = \
        [[[[False] * m for _ in range(n)] for _ in range(m)] for _ in range(n)]
    visited[red[X]][red[Y]][blue[X]][blue[Y]] = True

    print(bfs([red, blue, 1]))

 구슬 탈출 2의 문제는 해당 코드에서 bfs의 반환값을 찾지 못할 경우 -1, 찾을 경우 cnt 값을 반환하면 된다.