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

Signal이란 객체를 만들어 풀었다.

Signal은 방향, 움직임수, 행, 열으로 구성되어 있다.

(방향 U, R, D, L는 각각 0, 1, 2, 3으로 치환해서 풀었다.)

 

가장 중요시 봐야할 점은, 바로 재방문 했을 때를 잘 구분해야한다.

거울에 도달했을 때 진정 재방문인지를 잘 생각해야한다.

2차원으로 생각하다보면 이는 방향이 엇갈릴 때도 재방문으로 잘못 여길 수 있다.

(예제 입력 2를 생각해보면 이해가 될 것이다.)

 

때문에 나는 visited라는 배열을 3차원으로 정의했다.

(visited[시그널의 방향][시그널 row][시그널 column])

 

처음 그 궤도로 진입했을 때의 시그널의 방향과

어쩌다가 무한궤도로 시그널이 들어왔을 때의 방향은 다를 수 있기 때문이다.

이를 3차원 배열 visited로 구분짓는 것이다.

 

정답 소스코드

#include<bits/stdc++.h>
#define Voyager 1004
using namespace std;

const int maxN=504;

int intDirection[4][2] = { {-1,0}, {0,1}, {1,0}, {0,-1} };
char charDirection[4] = {'U', 'R', 'D', 'L'};
struct Signal {
    int direction;
    int movements;
    int row;
    int column;

    Signal() {}

    Signal(int pdirection, int pmovements, int prow, int pcolumn) {
        direction=pdirection;
        movements=pmovements;
        row=prow;
        column=pcolumn;
    }
};

int N, M;
char arr[maxN][maxN];
int PR, PC;

int visited[4][maxN][maxN];

void input() {
    cin>>N>>M;
    for(int i=1; i<=N; i++)
        for(int j=1; j<=M; j++)
            cin>>arr[i][j];
    cin>>PR>>PC;
}

bool isMovable(Signal signal) {
    if(signal.row>=1 && signal.row<=N && signal.column>=1 && signal.column<=M) {
        if(arr[signal.row][signal.column]=='C')
            return false;
        return true;
    }
    return false;
}

int move(Signal signal) {
    visited[signal.direction][signal.row][signal.column]=signal.movements;
    return signal.movements;
}

Signal makeNewSignal(Signal current) {
    Signal next;

    if(arr[current.row][current.column]=='/') {
        if(current.direction%2==0)
            next.direction=current.direction+1;
        else
            next.direction=current.direction-1;
    }
    else if(arr[current.row][current.column]=='\\')
        next.direction=3-current.direction;
    else
        next.direction=current.direction;

    next.movements=current.movements+1;

    next.row=current.row+intDirection[next.direction][0];
    next.column=current.column+intDirection[next.direction][1];

    return next;
}

void solve() {
    char res1='U';
    int res2=0;

    for(int i=0; i<4; i++) {
        memset(visited, 0, sizeof visited);
        Signal signal(i, 1, PR, PC);
        while(isMovable(signal)) {
            if(visited[signal.direction][signal.row][signal.column]>0) {
                cout<<charDirection[signal.direction]<<"\n"<<"Voyager\n";
                return;
            }

            int tmp=move(signal);

            if(tmp>res2) {
                res1=charDirection[i];
                res2=tmp;
            }

            signal=makeNewSignal(signal);
        }
    }

    cout<<res1<<"\n"<<res2<<"\n";
}

int main() {
    ios_base::sync_with_stdio(0);
    input();
    solve();
    return 0;
}