BOJ 3987 - VOYAGER (보이저 1호)

* BOJ 3987 - VOYAGER (보이저 1호, https://www.acmicpc.net/problem/3987)

  [ 분류 없음 ]

  

  지정된 좌표에서 시작해서 상하좌우 방향으로 진행할 때, 가장 많은 칸을 밟을 수 있는 것이 답이 된다.

  이전 포스팅과 비슷한 문제이긴 하다.

  방향이 좌표당 4개가 있기 때문에 해당 방향으로 또 방문한다면 이를 사이클로 보자.

  사이클이 존재한다면 무한히 반복할 수 있기 때문에 Voyager를 출력해야 한다. 단, 그 무한히 반복할 수 있을 때의 처음 방향을 출력해야 한다. 가령 오른쪽으로 시작했을 때 반복이 된다면 아래처럼 출력한다.

R

Voyager

- 코드

#include <cstdio>
#include <cstring>
int main() {
	char board[500][501], dirp[]="URDL";
	int N, M, i, j, dy[] = { -1,0,1,0 }, dx[] = { 0,1,0,-1 }, ans = 0, dir = 0, vi[500][501][4],t,sy,sx,cy,cx,d,ty,tx,td;
	bool cycle = 0;
	scanf("%d%d", &N, &M);
	for (i = 0; i < N; i++) scanf("%s", board[i]);
	scanf("%d%d", &sy, &sx);
	sy--, sx--;
	for (i = 0; i < 4; i++) {
		memset(vi, 0, sizeof vi);
		cy = sy, cx = sx;
		t = vi[cy][cx][i] = 1, td = d = i;
		while (1) {
			ty = cy + dy[d], tx = cx + dx[d];
			if (!(0 <= ty && ty < N && 0 <= tx && tx < M && board[ty][tx] != 'C')) break;
			if (board[ty][tx] != '.') {
				if (board[ty][tx] == '/') td = (d + (d % 2 ? 3 : 1)) % 4;
				else {
					switch (d) {
					case 0: td = 3; break;
					case 1: td = 2; break;
					case 2: td = 1; break;
					case 3: td = 0; break;
					}
				}
			}
			if (vi[ty][tx][td]) {
				cycle = 1;
				dir = i;
				break;
			}

			vi[ty][tx][td] = vi[cy][cx][d] + 1;
			t++;
			cy = ty, cx = tx, d = td;
		}
		if (ans < t) {
			ans = t, dir = i;
			if (cycle) break;
		}
	}
	printf("%c\n", dirp[dir]);
	if (cycle) puts("Voyager");
	else printf("%d", ans);
	return 0;
}