백준: 15644 구슬 탈출 3

문제

15644번: 구슬 탈출 3

 

문제 풀이

 앞서 다룬 문제인 구슬 탈출을 이해하고 있다면, 쉽게 풀 수 있는 문제이다. 이전의 문제와 다른 점이 있다면 구슬 탈출 2의 문제에서 이동 경로도 함께 출력하는 것이다. visited의 경우 단순히 방문 여부를 체크하는 False / True 형태로 선언할 수도 있지만, visited를 문자로 선언하게 되면 각 방문에 따라 방문 경로를 확인할 수 있다. 

 

dirs = {'R': (0, 1), 'L': (0, -1), 'D': (1, 0), 'U': (-1, 0)}

 기울인 방향에 따라, 경로를 추적하기 위해 딕셔너리를 활용하여 방향 탐색을 진행하면 쉽게 처리할 수 있다.

 

코드

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 = {'R': (0, 1), 'L': (0, -1), 'D': (1, 0), 'U': (-1, 0)}

    while q:
        r, b, cnt = q.popleft()
        path = visited[r[X]][r[Y]][b[X]][b[Y]]

        if cnt > 10:
            break

        for move in dirs:
            dx, dy = dirs[move]
            next_path = path + move
            next_red, red_cnt = move_beads(r, dx, dy)
            next_blue, blue_cnt = move_beads(b, dx, dy)
            # 파란색 구슬이 먼저 탈출하는 경우의 수 제외.
            if graph[next_blue[X]][next_blue[Y]] == 'O':
                continue
            # 빨간 구슬이 먼저 탈출 가능한 경우
            if graph[next_red[X]][next_red[Y]] == 'O':
                # 구슬을 찾은 경우
                # 시도 횟수, INIT 문자를 제외한 나머지를 반환.
                return cnt, next_path[4:]

            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] = next_path
                q.append([[r_x, r_y], [b_x, b_y], cnt + 1])

    return -1, None


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 = \
        [[[[''] * m for _ in range(n)] for _ in range(m)] for _ in range(n)]
    visited[red[X]][red[Y]][blue[X]][blue[Y]] = 'INIT'

    for ret in bfs([red, blue, 1]):
        if ret is not None:
            print(ret)

 초기에 빨간 구슬, 파란 구슬의 경로(시작점)에 재방문 하지 않기 위해, 해당 좌표를 INIT로 초기화 하였다. 따라서 탈출 가능한 경우에는 INIT를 제외한 나머지 경로를 출력하여야 한다.