[C++] 텀 프로젝트 (백준 9466번)

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

 

이 문제는 사이클을 판단하는 문제이다. 

 

사이클이 있는지 없는지를 판단하기 위해서 chk 배열과 v 변수를 두었다.

v 변수는 현재가 몇번째 연결 그래프인지를 저장하는 변수이고, chk 배열은 해당 노드를 방문 했는지 여부와 몇번째 연결 그래프에서 방문했는지를 저장하는 배열이다. 

 

해당 연결 그래프에서 사이클이 존재하는지를 판단했다면 이제 어느 노드부터 어느 노드까지가 사이클인지 알아야 한다.

이를 위해서 지나온 경로를 기록한 후 사이클의 기준점까지 역주척하면서 체크하면 되는데, 두 가지 방법이 있다. 하나는 재귀 함수의 콜 스택을 사용하는 방법이고, 다른 하나는 명시적 스택(stack 자료구조)을 사용하는 방법이다. 

 

1. 재귀 함수 콜 스택 사용

#include <iostream>
#include <vector>
using namespace std;

int n, v, ce;
vector<int> a;
vector<int> chk;
vector<bool> iscycle;

void dfs(int cur) {
    chk[cur] = v;
    int nxt = a[cur];
    if (chk[nxt] == -1) dfs(nxt);
    else if (chk[nxt] == chk[cur]) ce = nxt; // cycle의 기준점을 저장
    if (ce >= 0) {
        iscycle[cur] = 1;
        if (ce == cur) ce = -1; // 여기서부터는 cycle이 아니라고 표시
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;

    while (t--) {
        cin >> n;
        a.resize(n + 1);
        chk.assign(n + 1, -1);
        iscycle.assign(n + 1, 0);

        for (int i = 1; i < n + 1; i++) cin >> a[i];

        for (int i = 1; i < n + 1; i++) {
            if (chk[i] >= 0) continue; // 방문한 적 없으면 패스
            ce = -1;
            dfs(i);
            v++;
        }

        int ans = 0;
        for (int i = 1; i < n + 1; i++) {
            if (!iscycle[i]) ans++;
        }
        cout << ans << '\n';
    }
}

2. 명시적 스택 사용

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int n, v, ce;
vector<int> a;
vector<int> chk;
vector<bool> iscycle;
stack<int> path;

void dfs(int cur) {
    chk[cur] = v;
    path.push(cur); // 스택에 경로 넣어두기
    int nxt = a[cur];
    if (chk[nxt] == -1) {
        dfs(nxt);
    } else if (chk[nxt] == chk[cur]) {
        while (path.top() != nxt) { // nxt일 때까지 pop하면서 iscycle에 체크
            iscycle[path.top()] = 1;
            path.pop();
        }
        iscycle[path.top()] = 1;
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;

    while (t--) {
        cin >> n;
        a.resize(n + 1);
        chk.assign(n + 1, -1);
        iscycle.assign(n + 1, 0);
        path = stack<int>();

        for (int i = 1; i < n + 1; i++) cin >> a[i];

        for (int i = 1; i < n + 1; i++) {
            if (chk[i] >= 0) continue; // 방문한 적 없으면 패스
            ce = -1;
            dfs(i);
            v++;
        }

        int ans = 0;
        for (int i = 1; i < n + 1; i++) {
            if (!iscycle[i]) ans++;
        }
        cout << ans << '\n';
    }
}

(AC)