BOJ 5829 ) Luxury River Cruise

 

5829번: Luxury River Cruise

 Corn Maze도 그렇고 이 문제도 그렇고 소가 나온다. 여기서는 농부 John이 소들과 Bessie를 데리고 배를 타고 강을 돈다. 이 농부는 항구에 도착하면 왼쪽 또는 오른쪽을 택해서 다시 항해를 시작하는데 왼쪽 또는 오른쪽을 고르는 시퀀스가 주어진다. Bessie는 이 시퀀스가 K회 반복되고나서 어디에 있을지 알고싶어한다. 사실 영어 문제라 정확한 해석인지는 모르겠으나 이정도면 문제 푸는데는 지장이 없으니 대강 풀었다. 

 일단 K가 최대 10^9이고 M은 최대 500이니까 K는 반복되는 부분을 찾아서 모듈러연산을 해주어야 한다. 나는 여기서 문제를 내 마음대로 의역을 하는 바람에 한참 헤맸다. 

강을 빙빙 돈다고 하길래 당연히 좌측의 형태로 생각했다. 예제가 저것과 비슷한 형태였는데 다른 경우를 아예 고려를 하지 않은 것이다. 그렇게 생각을 하니까 L과 R이 서로 상쇄가 되었고 사이클이 N회마다 돌아서 굉장히 편안한 문제라고 생각하고 제출했는데 자꾸 틀려서 학회 슬랙에 도움을 요청햇더니 우측과 같은 경우도 고려해야 한다고 하셔서 그제서야 우측 경우를 고려했다. 1232323과 같이 사이클에 모든 정점이 포함되지 않는 경우도 존재하고 L과 R이 서로 상쇄가 되지도 않았다. 어떻게 사이클을 파악할 수 있을까 고민하다가 각 정점에 방문 체크와 몇번째 반복에서 방문했는지를 기록했다. 한 번 방문했던 정점에 다시 방문을 한 경우 하나의 사이클이 생성됬다는 것이므로

(사이클의 길이) = (현재 회차) - (이전 방문 회차)

 로 사이클의 길이를 얻을 수 있었다. 그리고 남은 회차는 모두 사이클의 반복이므로

(남은회차)%=(사이클의 길이)

 로 연산 횟수를 줄여 답을 구할 수 있었다. 문제를 의역하지 않는 습관을 들여야 하는데 자꾸 제멋대로 해석해서 큰일이다. 

#include <iostream>
#include <vector>
#define pii pair<int,int>
using namespace std;
int N, M, F, S;
long long K;
pii visited[1004];
vector<vector<int>> river;  
vector<int> seq;

int sailing(int port){
    int i=0;
        while(i<K){
            for(int j=0;j<M;j++){
                port=river[port][seq[j]];
            }
            i++;
            if(visited[port].first==1){
                F=visited[port].second;
                S=i;
                break;
            }
            visited[port].first=1;  // 방문체크
            visited[port].second=i; // 몇번째 반복에 오게되는지 체크
        }
        if(i!=K){
            K=K-i;
            K=K%(S-F);  // S-F : 사이클의 길이. K가 최대 10^9이므로 %연산.
            while(K--){
                for(int j=0;j<M;j++){
                    port=river[port][seq[j]];
                }
            }
    }
    return port;
}

int main(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    cin>>N>>M>>K;
    river=vector<vector<int>>(N+2,vector<int> (2));
    int L,R;
    for(int i=1;i<=N;i++){
        cin>>L>>R;
        river[i][0]=L;
        river[i][1]=R; 
    }
    char temp;
    for(int i=0;i<M;i++){
        cin>>temp;
        if(temp=='L')seq.push_back(0);	// L
        else seq.push_back(1);			// R
    }  
    cout<<sailing(1);
}