9466 텀 프로젝트

BOJ::9466 텀 프로젝트

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

dfs를 통해 사이클을 찾아주어야 하는 문제.

무턱대로 탐색하면 시간초과가 난다.

나는 vector와 check배열을 이용해 중복방문 하지 않도록 탐색했다.

1번째 방법.

#include <iostream>
#include <vector>
#include <memory.h>
using namespace std;
 
int t, n;
int map[100001];
bool check[100001];
vector<int> v;
 
void dfs(int x, int sx) {
    //시작점과 같아지는 경우
    if (x == sx) {
        //이제까지 방문한 곳들 사이클여부 확인
        for (int i = 0; i < v.size(); i++) {
            map[v[i]] = 0;
        }
    }
    else {
        //이미 사이클이거나 방문했거나
        if (map[x] == 0 || check[x]) return;
 
        check[x] = true;
        v.push_back(x);
        dfs(map[x], sx);
    }
}
 
int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
 
    cin >> t;
    while (t--) {
        cin >> n;
 
        for (int i = 1; i <= n; i++) {
            cin >> map[i];
        }
 
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            //사이클인 번호
            if (map[i] == 0) continue;
            if (map[i] == i) {
                map[i] = 0;
                continue;
            }
            //벡터 초기화
            v.clear();
 
            //벡터에 인덱스 넣어주고 check배열로 체크
            v.push_back(i);
            check[i] = true;
            //사이클 탐색하기
            dfs(map[i], i);
            //check배열 초기화
            for (int i = 0; i < v.size(); i++) {
                check[v[i]] = false;
            }
            //i로부터 탐색해서 사이클 못찾은 경우
            if (map[i] != 0) {
                map[i] = 0;
                cnt++;
            }
        }
 
        cout << cnt << "\n";
    }
}

2번째 방법.

#include <stdio.h>
using namespace std;
 
int a[100001];
bool check[100001];
int visited[100001];
bool cycle[100001];
int t, n,cnt,sum;
 
void init() {
    for (int i = 1; i <= n; i++) {
        check[i] = false;
        cycle[i] = false;
    }
}
 
//탐색하면서 cycle찾음
void dfs(int v) {
    cnt++;
    if (check[v]) {
        int idx = 0;
        for (int i = 1; i < cnt; i++) {
            if (visited[i] == v) {
                idx = i;
                for (int i = idx; i < cnt; i++) {
                    cycle[visited[i]] = true;
                }
                break;
            }
        }
        return ;
    }
    visited[cnt] = v;
    check[v] = true;
    dfs(a[v]);
}
 
int main() {
    scanf("%d", &t);
    for (int tc = 0; tc < t; tc++) {
        scanf("%d", &n);
        
        init();
 
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
        }
 
        for (int i = 1; i <= n; i++) {
            if (!check[i]) {
                cnt = 0;
                dfs(i);
            }
        }
 
        sum = 0;
        for (int i = 1; i <= n; i++) {
            if (!cycle[i]) {
                sum++;
            }
        }
        printf("%d\n", sum);
    }
}