BOJ 11657 [타임머신]

BOJ 11657 : www.acmicpc.net/problem/11657

11657번: 타임머신

처음에 queue에 넣어서 bfs처럼 풀어보려고 시도했으나, cycle을 알아낼 마땅한 방법이 떠오르지 않아 재귀 형식으로 바꿨다.

 

key point는 재귀함수 내의 if문이다.

• 현재 재귀호출하면서 방문한 적 없는가?
• 현재 재귀 내에서 방문한 적이 없더라도, 이전에 방문했을 때 저장된 값(arr)보다 적은 시간이 걸리는가?

이 두가지를 따져가며 풀 수 있었다.

 

 

 

 

먼저 1을 방문한다. 1의 다음 도시는 2, 3인데 2부터 방문해본다.

 

방문한 적 없으니 2로 들어가되, 현재 도달한 시간이 저장된 값보다 작으므로 업데이트한다.

 

3도 방문한 적 없으니 방문체크 하고, 저장된 값보다 작으므로 업데이트한다.

 

현재 가지에서 1을 방문한 적이 있다. cycle을 찾았으니 이제 시간을 무한히 줄일 수 있는지가 관건이다.
현재 저장한 값보다 작으면 무한히 작아질 수 있다.

 

나아가다 보면 재귀에서 빠져나올 때 마다 방문체크를 풀어준다.

다시 줄기를 시작했을 때 저장된 시간을 계속 체크하며 업데이트 해준다. 

#include <iostream>
#include <vector>
#include <limits.h>
using namespace std;
 
int arr[501];
bool visited[501];
 
struct City {
public:
    int destination, distance;
};
vector<vector<City>> cities;
 
int result = 0;
void recursive(int current) {
    for (City c : cities[current]) {
        int next = c.destination;
        int dist = c.distance;
        if (!visited[next]) {
            visited[next] = true;
            
            if (arr[next] > arr[current] + dist) {
                arr[next] = arr[current] + dist;
                dfs(next);
            }
            visited[next] = false;
        }
        else {
            if (arr[next] > arr[current] + dist) {
                result = -1;
                return;
            }
        }
    }
}
int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
 
    int N, M;
    cin >> N >> M;
    
    cities.resize(N + 1);
    fill_n(arr, N + 1, INT_MAX);
    arr[1] = 0;
    for (int busIdx = 0; busIdx < M; busIdx++) {
        
        int A, B, C;
        cin >> A >> B >> C;
        City city;
        city.destination = B;
        city.distance = C;
        cities[A].push_back(city);
    }
    visited[1] = true;
    
    dfs(1);
    
    if (result == -1) {
        cout << result << "\n";
    }
    else {
        for (int i = 2; i <= N; i++) {
            if (arr[i] == INT_MAX) {
                cout << "-1\n";
            }
            else {
                cout << arr[i] << "\n";
            }
        }
    }
    return 0;
}