BOJ 9466번 텀 프로젝트

BOJ : https://www.acmicpc.net/problem/9466

GitHub : https://github.com/junho0956/Algorithm/blob/master/9466/9466/%EC%86%8C%EC%8A%A4.cpp

 

텀 프로젝트

문제는 이해하는데 어려움이 없을 것이다.

 

** 시간을 빠르게 해결하기 위한 방법이 필요하다 **

** 이 문제의 경우 한 테스트케이스 당 O(N) 에 맞먹는 속도로 풀어내야 문제해결이 가능하다 **

** 나도 그랬지만 간혹 문제를 다 풀고 제출하니 메모리초과가 뜨는 경우가 많은데

이 경우는 스택오버플로 문제일 것이다. ==> dfs 의 깊이가 끝없이 이어진다는 소리

아마 이 예제를 넣어보면 메모리초과에 대한 문제를 해결할 수 있을 것이다.

1

3

2 3 2 **

** O(N) 으로 탐색하라는 말이 어떤식으로 흘러가야되는건지 잘 파악해보자 **

 

#include <iostream>
using namespace std;
#define cur 111111
 
int arr[100001];
int checking[100001];
int T, n, person, find_num;
 
bool dfs(int now, int go, int ii) {
    if (checking[now]) return false;
    checking[now] = cur + ii;
 
    if (checking[go]) {
        if (checking[go] == cur + ii) {
            find_num = go; 
            checking[now] -= cur;
            if (now == go) return false;
            return true; 
        }
        else return false;
    }
 
    if (dfs(go, arr[go], ii)) {
        checking[now] -= cur;
        if (now != find_num) return true;
        else return false;
    }
 
    return false;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    cin >> T;
    while (T--) {
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> person;
            arr[i] = person;
        }
 
        for (int i = 1; i <= n; i++) {
            if (!checking[i]) {
                find_num = 0;
                if (dfs(i, arr[i], i) && i == find_num) checking[i] -= cur;
            }
        }
 
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            if (checking[i] > cur) cnt++;
            checking[i] = 0;
        }
 
        cout << cnt << "\n";
    }
 
    return 0;
}