백준 5829번 Luxury River Cruise

USACO 2013 Open Contest Silver 2번 문제이다.

문제 요약

정점이 N개 주어지고, N개의 정점은 각각 두 개의 간선을 갖는다. 정점의 각 간선은 Left와 Right로 나타내어진다. 길이 M의 Left 혹은 Right로 이루어진 순열이 주어지는데, 1번 정점에서 출발하여 M개의 순열을 K번 반복했을 때 도착하는 정점의 번호를 출력하는 것이 문제이다.

문제의 제한은 $ 1 \le N \le 1000, 1 \le M \le 500, 1 \le K \le 10^9$이다.

풀이

당연히 그래프를 만들고 $ MK $번 간선을 타고 지나가면 시간 초과다. 일단 이걸 줄여보자. 길이 $M$짜리 순열을 $K$번 타고 지나간 뒤의 결과를 찾는 것인데, 하나의 정점에서 간선을 $M$번 타고 가다가 그 중간에서 끝나는 경우는 존재하지 않는다. 그리고, 그래프는 중간에 변하지 않으므로 한 정점에서 간선을 $M$번 타고 지나간 결과는 절대 바뀌지 않는다.

이를 이용해서 각 정점에서 간선을 $M$번 타고 지나간 결과를 계산해주고 도착점과 시작점을 이어주어 새로운 그래프를 만들자. 예제로 주어진 그래프라면 1->2, 2->3, 3->4, 4->1과 같은 간선을 가지는 그래프로 변한다. 이제 이 그래프에서 1번부터 출발해서 간선을 $K$번 타면 답을 알 수 있다.

그런데 $K$가 $10^9$로 일일이 다 돌기엔 너무 크다. 새로 만든 그래프를 잘 살펴보자. 이 그래프는 정점이 $N$개면서 각 정점의 차수가 1인 유향 그래프이다. 그리고 원래 여러개의 컴포넌트들을 축약 시켜놓은 것이다. 이걸 잘 생각해보면, 그래프는 사이클을 가질 수 밖에 없다는 사실을 알 수 있다.

이를 이용해서 1번부터 출발해서 사이클의 시작점과 사이클의 길이를 찾아내면 답을 구할 수 있다.

시간복잡도를 계산해보자. 먼저 새로운 그래프를 만드는 데에 각 정점마다 간선을 $M$번씩 타고 지나가기 때문에 $O(NM)$.

새로 만들어진 그래프에서 1번 정점이 속해있는 사이클을 찾는데, 이 사이클의 길이는 길어봤자 $N$이기 때문에 $O(N)$이 걸린다.

따라서 총 시간복잡도는 $O(NM+N)$으로 아주 빠르게 끝낼 수 있다.

아래는 코드다. 항상 까먹기 쉬운 사실이지만, 이전 숫자에 따라 어떤 일정한 규칙에 맞춰 생성되는 수열은 꼭 수열의 시작부터 사이클이 생성되는 것이 아니라 중간부터 시작할 수도 있다는 것이다. $ \rho $문자 처럼 말이다.

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

ll N, M, K;
int adj[1005][2];
bool vis[1005];
vector<int> path;
vector<int> G(1005);

void dfs(int start, int cur, int idx) {
    if(idx == M) {
        G[start] = cur; return ;
    }
    int nxt = adj[cur][path[idx]];
    dfs(start, nxt, idx+1);
}

int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    cin >> N >> M >> K;
    for(int i=1;i<=N;++i) {
        int l, r;
        cin >> l >> r;
        adj[i][0] = l; adj[i][1] = r;
    }
    for(int i=0;i<M;++i) {
        string s;
        cin >> s;
        if(s[0] == 'L') path.push_back(0);
        else path.push_back(1);
    }
    for(int i=1;i<=N;++i) dfs(i,i,0);
    int cur = 1;
    int len = 0;
    int start;
    for(int i=0;i<=N;++i) {
        if(vis[cur]) {
            start = cur; len = i; break;
        }
        vis[cur] = true;
        cur = G[cur];
    }
    cur = 1;
    for(int i=0;i<=N;++i) {
        if(cur == start) {
            len -= i;
            break;
        }
        cur = G[cur];
        --K;
        if(K == 0) break;
    }
    if(K == 0) {
        cout << cur << '\n';
        return 0;
    }
    K %= len;
    cur = start;
    while(K--) cur = G[cur];
    cout << cur << '\n';
    return 0;
}