26. SW_Test 연습 백준 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"를 출력한다.

 

#pragma warning (disable :4996)
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
char Map[500][500];
int N, M;
int PR, PC;
int maxnum;
int maxdir;
int dir[4][2] = { {-1,0}, {1,0}, {0,-1} ,{0,1} };
char Dir[4] = { 'U','D','L','R' };
void go(int y, int x , int d) {
	int cundir = d;
	int cuny = y;
	int cunx = x;
	int cnt = 1;
	while (true){
		int nextY = cuny + dir[cundir][0];
		int nextX = cunx + dir[cundir][1];
		if (nextY < 0 || nextY >= N || nextX < 0 || nextX >= M) {
			break;
		}
		if (x == nextX && y == nextY && d == cundir) {
			cout << Dir[d] << endl;
			cout << "Voyager" ;
			exit(0);
		}
		if (Map[nextY][nextX] =='C') {
			break;
		}
		if (Map[nextY][nextX] == '/') {
			if (cundir ==0) {
				cundir = 3;
			}
			else if (cundir == 1) {
				cundir = 2;
			}
			else if (cundir == 2) {
				cundir = 1;
			}
			else {
				cundir = 0;
			}
		}
		if (Map[nextY][nextX] == '\\') {
			if (cundir == 0) {
				cundir = 2;
			}
			else if (cundir == 1) {
				cundir = 3;
			}
			else if (cundir == 2) {
				cundir = 0;
			}
			else {
				cundir = 1;
			}
		}
		cuny = nextY;
		cunx = nextX;
		cnt++;
	}
	if (maxnum < cnt) {
		maxnum = cnt;
		maxdir = d;
	}
}
int main() {
	freopen("input.txt", "r", stdin);
	cin >> N >> M;
	for (int i = 0; i < N;i++) {
		for (int j = 0; j < M; j++) {
			cin >> Map[i][j];
		}
	}
	cin >> PR >> PC;
	PR = PR - 1;
	PC = PC - 1;
	go(PR, PC, 0);
	go(PR, PC, 3);
	go(PR, PC, 1);
	go(PR, PC, 2);
	cout << Dir[maxdir] << endl;
	cout << maxnum ;
	return 0;
}