[BOJ] 백준 3987 보이저 1호

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

 Input 

5 5

../.\

.....

.C...

...C.

\.../

3 3

 

 Output 

U

17

문제 조건 중 같은 시간일 경우 U, R, D, L의 순서 중 앞서는 것을 출력해야 하므로

U → R → D → L 순서대로 시뮬레이션 해서 신호 전달횟수가 커지는 경우만 갱신

 

시그널이 항성계 내에 무한히 존재할 수 있는 경우가 있다고 하는데,

행성 배치에 따라서 동일한 지점을 다른 방향으로 접근할 수 있는데

이전에 들렸던 위치를 다시 방문했을 때, 그때의 시그널의 방향과 현재의 시그널의 방향이 같은 경우에

특정 구간을 무한히 전파되는것으로 간주할 수 있습니다.

bool visited[x][y][dir] = (x, y) 지점을 dir 방향으로 접근 여부로 처리할 수 있지만,

전파되는 방식을 고려하면 무한히 전파되는 경우를 처음 시작점에서 출발한 방향을 

다시 동일한 방향으로 거쳐가는 경우일 수 밖에 없습니다.

 

---

#include <iostream>
using namespace std;
 
int N, M, ansCnt, ansDir;
char direction[] = { 'U', 'R', 'D', 'L' };
char map[502][502];
int dx[] = { -1, 0, 1, 0 };
int dy[] = { 0, 1, 0, -1 };
bool isVoyager;
 
void sendSiganl(int startX, int startY, int startDir) {
    int x = startX, y = startY;
    int cnt = 1; int dir = startDir;
 
    while (1) {
        x = x + dx[dir];
        y = y + dy[dir];
 
        // 항성계를 벗어나거나 블랙홀을 만난 경우
        if (x <= 0 || y <= 0 || x > N || y > M || map[x][y] == 'C') {
            if (ansCnt < cnt) {
                ansCnt = cnt;
                ansDir = startDir;
            }
            return;
        
        }
        // 처음 출발한 지점을 동일한 방향으로 접근한 경우
        if (x == startX && y == startY && dir == startDir) {
            ansDir = startDir;
            isVoyager = true;
            return;
        }
 
        // 방향 전환
        if (map[x][y] == '/') dir = 1 ^ dir;
        else if (map[x][y] == '\\') dir = 3 - dir;
 
        cnt++;
    }
}
 
int main() {
    cin >> N >> M;
 
    // 항성계를 에워싸고 있는 테두리 = 0
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= M; ++j) {
            cin >> map[i][j];
        }
    }
    int startX, startY;
    cin >> startX >> startY;
 
    for (int startDir = 0; startDir < 4; startDir++) {
        if (!isVoyager) 
            sendSiganl(startX, startY, startDir);
    }
 
    cout << direction[ansDir] << "\n";
    if (isVoyager) cout << "Voyager";
    else  cout << ansCnt;
}