백준 5829(Luxury River Cruise)

www.acmicpc.net/problem/5829

5829번: Luxury River Cruise

일단 스터디에서 진행하고 있는 문제여서 풀어보았다. 

 

처음에는 핵심을 잡았던 것 같다. 

 

하지만 문제에서 무엇을 물어보는건지도 제대로 몰랐고, 코포처럼 간단히 생각해보자 했더니 빙빙 도는거니깐 그냥 뚝딱하면 풀릴 것 같은 느낌이 들어서 뚝딱 했지만 실패

 

그리고 계속 생각을 해보았지만 아무리 생각을 해보아도 주기의 범위가 눈에 보이질 않았다. 

 

그러다가 그냥 언뜻 생각났던 것 같다. 아니 그냥 할 수 있는거, 지금 알고 있는 거, 꼭 알아야 하는 것 등을 적고 생각을 해보니 생각이 난 것 같다. 

 

예제로 설명을 하자 

 

4 3 3

2 4

3 1

4 2

1 3

L L R

 

1(시작) -> 2 -> 3 -> 2(시작) -> 3 -> 4 -> 3(시작) -> 4 -> 1 -> 4

-> 1 -> 2 -> 1(시작)

 

어떤 점에서 시작을 한다고 하고, 그 점에서 이미 시작을 하였다면 주기반복이다. 

왜냐면 어떤 점에서 M의 이동을 하여서 목적지로 이동을 한다고 하면 M의 순서는 변하지 않고, 그래프도 그대로 있으니깐 당연하다. 

 

따라서 주기를 찾으려면 일단 모든 시작점에서 M번의 간선을 지났을 때 목적지를 구하고, 

최대 N번의 반복으로 주기를 찾는다. 

 

이 주기를 찾고 나면 

 

어떤 지점에서 주기가 시작되는지 잘 생각해보고 코드를 구현하면 된다. 

 

사실 위에 주기가 최대 N이라는 것만 생각나는 순간 풀 수 있는 문제가 아닐까 생각한다. 

 

#include<iostream>
using namespace std;
#define MAX 1005

int N, M, K;
int adj[MAX][2];
int mov[MAX];
int togo[MAX];
int G[MAX];
bool check[MAX];

void route(int idx, int start, int cur) {
	if (idx == M) {
		togo[start] = cur;
		return;
	}

	int rl = mov[idx];
	int nxt = adj[cur][rl];
	route(idx + 1, start, nxt);
}

int main() {
	cin >> N >> M >> K;
	for (int i = 1; i <= N; i++) {
		int a, b;
		cin >> a >> b;
		adj[i][0] = a;
		adj[i][1] = b;
	}

	for (int i = 0; i < M; i++) {
		char a;
		cin >> a;
		if (a == 'L') {
			mov[i] = 0;
		}
		else {
			mov[i] = 1;
		}
	}
	for (int i = 1; i <= N; i++) {
		route(0, i, i);
	}
	int start = 1;
	int length=0, T=0;
	for (int i = 0; i <= N; i++) {
		if (check[start]) {
			length = i;
			T = i - G[start];
			break;
		}
		G[start] = i;
		check[start] = true;
		start = togo[start];
	}
	int st = length - T;
	if (T<=K) {
		K -= st;
		K %= T;
	}
	int num = st + K;
	int ans=1;
	while (num--) {
		ans = togo[ans];
	}
	cout << ans << '\n';
}