[C++] 백준 3987 - 보이저 1호

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

3987번: 보이저 1호

<풀이>

1. 항성계를 입력 받고, 시작점부터 4방향(동,서,남,북) 차례차례 시그널을 보낸다.

2. 각 방향마다 시그널이 어떻게 가는지 구현하고, 결과를 저장한다.

3. 결과를 출력한다.

​

<해법>

1. 시그널이 무한히 전파될 수 있는 경우 구하는 방법.

=> 시그널이 '이전에 방문했던 좌표'를 '똑같은 방향'으로 방문했을 때, 시그널이 무한히 전파될 수 있는 경우가 됩니다.(코드의 visited배열을 사용)

#include <iostream>
#include <cstring>
using namespace std;
 
int di[] = { -1,0,1,0 };
int dj[] = { 0,1,0,-1 };
int changeDir_1[] = { 1,0,3,2 };
int changeDir_2[] = { 3,2,1,0 };
 
int N, M;
char map[502][502];
bool visited[502][502][4];
int si, sj;
 
char resDir[] = { 'U','R','D','L' };
int resTime = 0;
int resDirIndex;
bool isVoyager = false;
 
int main() {
 
    //입력
    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cin >> map[i][j];
        }
    }
    cin >> si >> sj;
 
    //시작점부터 4방향 탐색
    for (int i = 0; i < 4; i++) {
 
        //좌표, 방향, 시간, 방문 초기화
        memset(visited, false, sizeof(visited));
        int ni = si;
        int nj = sj;
        int dir = i;
        int time = 1;
        visited[si][sj][i] = true;
 
        while (true) {
 
            ni += di[dir];
            nj += dj[dir];
 
            //다음 시그널 위치가 범위를 넘어섰거나, 블랙홀을 만났을 경우 - 종료
            if (ni <= 0 || nj <= 0 || ni > N || nj > M || map[ni][nj] == 'C') {
                break;
            }
 
            //다음 시그널의 위치가 이전에 같은 방향으로 방문한적이 있을 경우 - 종료(Voyager)
            if (visited[ni][nj][dir]) {
                isVoyager = true;
                break;
            }
 
            //다음 시그널의 위치가 '.', '/', '\'일 경우 - 진행
            if (map[ni][nj] == '.') {
                
            }
            else if (map[ni][nj] == '/') {
                dir = changeDir_1[dir];
            }
            else {
                dir = changeDir_2[dir];
            }
            visited[ni][nj][dir] = true;
            time++;
        }
 
        //결과 저장
        if (isVoyager) {
            resDirIndex = i;
            break;
        }
        else {
            if (time > resTime) {
                resTime = time;
                resDirIndex = i;
            }
        }
    }
 
    //결과 출력
    if (isVoyager) {
        cout << resDir[resDirIndex] << "\n" << "Voyager";
    }
    else {
        cout << resDir[resDirIndex] << "\n" << resTime;
    }
}

 

시뮬레이션에 대해 알아볼 수 있는 문제였습니다.