[Python/BOJ] 3987. 보이저 1호

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

3987번: 보이저 1호

문제

보이저 1호는 1977년에 발사된 NASA의 태양계 무인 탐사선이다. 현재 보이저 1호는 태양권덮개 (헬리오시스)에 있다.

보이저 1호와 같이 오랜 기간동안 활동하는 탐사선은 경로를 항성계를 만날 때 마다 라디오 시그널 메시지를 이용해서 기록하고 있다.

항성계를 N * M개의 직사각형으로 나누어져 있는 N행 M열의 직사각형 그리드라고 생각해보자. 각 칸은 행성, 블랙홀을 포함할 수 있으며, 비어있을 수도 있다. 탐사선은 인접한 네 칸(위, 아래, 오른쪽, 왼쪽)중에서 하나를 골라서 시그널을 보낸다.

시그널은 항상 일직선으로 전파되며, 행성을 만났을 경우에는 전파되는 방향이 90도로 바뀌게 된다. 행성은 '/'와 '\'로 표현되는 두 종류가 있으며, 반사되는 법칙은 아래 그림과 같다.

시그널이 블랙홀이 있는 칸을 만나거나 항성계를 벗어날 때 까지 계속 전파된다. 시그널이 인접한 칸으로 이동하는데 걸리는 시간은 1초이다.

탐사선이 어느 방향으로 시그널을 보내면, 시그널이 항성계 내부에 있는 시간이 최대가 되는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ N, M ≤ 500)

다음 N개 줄에는 M개의 문자가 주어지며, '/'와 '\'는 행성을, C는 블랙홀을, '.'는 빈 칸을 나타낸다.

마지막 줄에는 탐사선이 있는 위치 PR과 PC가 주어진다. (1 ≤ PR ≤ N, 1 ≤ PC ≤ M)

출력

첫째 줄에 시그널을 보내는 방향을 출력한다. (U: 위, R: 오른쪽, D: 아래, L: 왼쪽)

만약, 방향이 여러 가지가 존재한다면, U, R, D, L의 순서 중 앞서는 것을 출력한다.

둘째 줄에는 가장 긴 시간을 출력한다. 만약, 시그널이 항성계 내에서 무한히 전파될 수 있다면 "Voyager"를 출력한다.

풀이

Code

import sys
input = sys.stdin.readline

def solution(n, m, graph, x, y) :
    # 1. 방향 재설정 함수 정의
    def next_direction(planet, direction) :
        # 1-1. 현재 방향이 U 일 경우
        if direction == 'U' : return 'R' if planet == '/' else 'L'
        # 1-2. 현재 방향이 R 일 경우
        elif direction == 'R' : return 'U' if planet == '/' else 'D'
        # 1-3. 현재 방향이 D 일 경우
        elif direction == 'D' : return 'L' if planet == '/' else 'R'
        # 1-4. 현재 방향이 L 일 경우
        else : return 'D' if planet == '/' else 'U'
    # 2. 시그널 유지 시간 함수 정의
    def return_time(direction) :
        # 2-1. 초기 위치 설정
        nx, ny = x, y
        # 2-2. 이전 경로 그래프 생성
        prior_graph = [[[] for _ in range(m)] for _ in range(n)]
        # 2-3.
        time = 0
        while True :
            # 2-3-1. 다음 위치 정의
            nnx, nny = nx + dirs[direction][0], ny + dirs[direction][1]
            # 2-3-2. 시간 카운팅
            time += 1
            # 2-3-3. 탈출 조건 설정
            if (nnx < 0 or nnx >= n or nny < 0 or nny >= m) or (graph[nnx][nny] == 'C') : break
            # 2-3-4. 현재 위치가 이전 위치에서 온 적 있는 경우
            if (nx, ny) in prior_graph[nnx][nny] :
                return 'Voyager'
            # 2-3-5. 이전 정보 삽입
            prior_graph[nnx][nny].append((nx, ny))
            # 2-3-6. 현재 위치가 행성일 경우 방향 변환
            if graph[nnx][nny] != '.' : direction = next_direction(graph[nnx][nny], direction)
            # 2-3-7. 현재 위치 업데이트
            nx, ny = nnx, nny
        # 2-4. 소요 시간 반환
        return time
    if graph[x][y] == 'C' :
        print('U')
        print(0)
    else :
        # 3. 방향 변수 생성
        dirs = {'U' : (-1, 0), 'R' : (0, 1), 'D' : (1, 0), 'L' : (0, -1)}
        # 4. 최종 방향, 시간 함수 정의
        ans_dir, ans_time = '', 0
        for direction in ['U', 'R', 'D', 'L'] :
            t = return_time(direction)
            if t == 'Voyager' or t > ans_time :
                # 방향, 시간 업데이트
                ans_dir, ans_time = direction, t
                if t == 'Voyager' : break
        # 5. 결과 출력
        print(ans_dir)
        print(ans_time)
        
if __name__ == "__main__" :
    n, m = map(int, input().split())
    graph = [input().rstrip() for _ in range(n)]
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    solution(n, m, graph, x, y)