[백준 5829번] [DFS] Luxury River Cruise

간단한 DFS문제이다.

 

사실 생각해보면 M을 기준으로 사이클 돌때를 판단해주면 된다.

주의해야할 지점은 바라보는 지점과 처리해야 하는 지점이 다르다는 것이다.

 

반복여부를 판단하기 위해서는 시작지점을 봐야하고, 문제에서 필요로하는 데이터는 1사이클의 마지막 데이터이기 때문이다.

 

다만, 일반적으로는 끝나는 데이터가 다시 시작지점이 되므로 이 부분을 핸들링해주면 되지만, 만약 1이 끝나는 지점의 경우는 예외 케이스가 발생할 수 있으므로 따로 처리해주면 된다.

 

추가적으로 가장 골치 아픈 지점이 다시 1로 돌아오는 것이 아니라 다른 지점으로 사이클을 형성하는 것이다.

이 부분을 해결하기 위해서 여러가지 방법이 있을 수 있다. pair 자료구조 등을 활용해서 처리할 수 있고 여러가지 방법이 존재한다.

따로 뺴서 계산하고 모듈러 처리해주면 된다.

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

using namespace std;

int N, M, K;

int visited[1001];
int arr[1001][2];
int cycle[501];
int count_value = 0;
int cycle_num = 1;
vector<int>  cycle_store;

void dfs(int start_node, int status){
    if(cycle_store.size() == K) return; // Early Exit

    int next_node = arr[start_node][cycle[status]];

    if(status == M - 1){
        status = -1;
        // Already visited
        if(visited[next_node] != 0){
            if(next_node == 1) cycle_store.push_back(next_node); // 예외처리
            cycle_num = cycle_store.size() - visited[next_node] + 1;        
            return;
        }
        visited[next_node] = ++count_value; // 방문처리
        cycle_store.push_back(next_node);
    }

    dfs(next_node, status + 1);
    return;
}

int main(void){
    fastio;
    memset(visited, 0, sizeof(visited));
    memset(arr, 0, sizeof(arr));
    memset(cycle, 0, sizeof(cycle));
    visited[1] = 1;

    cin >> N >> M >> K;

    for(int i = 1; i <= N; i++){
        cin >> arr[i][0] >> arr[i][1];
    }

    for(int i = 0; i < M; i++){
        char check;
        cin >> check;
        cycle[i] = (check == 'L') ? 0 : 1;
    } 

    dfs(1, 0);
    K -=  (cycle_store.size() - cycle_num);
    int print_check = K % cycle_num;
    if(print_check == 0){
        cout << cycle_store.back() << "\n";
    }
    else cout << cycle_store[print_check - 1 + cycle_store.size() - cycle_num] << "\n";

    return 0;
}