요즘 클래스 4 전부 미는 걸 목표로 하고 있는데 그 중에서 골드 3고 그래프길래 오? 이거 금방 풀지도ㅎ 하면서 패기넘치게 잡았던 문제다.

근데 시간 초과의 늪에서 헤어나오지 못하고 결국 gg침…^^

내가 시간초과를 얻었던 코드는 다음과 같다.

// 텀 프로젝트 - 골드 3

#include <bits/stdc++.h>

using namespace std;

int n;
vector<int> team;
vector<int> visited;

int cnt;
bool dfs(int start, int cur) {
    //처음이랑 같을 때 -> 팀 생김
    if (start == cur) {
        visited[cur] = 2;
        return true;
    }
    // 처음이랑 같은 경우 아니면서 다음 칸 가면 무한루프 -> 팀 안생김
    if (cur == team[cur]) {
        return false;
    }
    if (visited[cur] == 1) {
        visited[start] = 1;
        return false;
    }
    if (visited[cur] == 2) {
        return false;
    }
    //방문, 팀 배정 x
    visited[cur] = 1;
    cnt++;
    bool flag = dfs(start, team[cur]);
    //팀 배정 완료
    if (flag) visited[cur] = 2;
    else visited[cur] = 0;
    return flag;
}

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

    int t;
    cin >> t;

    while(t--) {
        cin >> n;
        team.assign(n+1, 0);
        for (int i = 1; i <= n; i++) {
            cin >> team[i];
        }
        visited.assign(n+1, false);
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            if (visited[i]) continue;
            cnt = 1;
            visited[i] = true;
            bool flag = dfs(i, team[i]);
            if (flag) ans += cnt;
        }
        cout << n-ans << '\n';
    }
}

코드 자체는 뭐… 보이는 그대로다. 근데 이 코드의 문제는… 한 번 탐색할 때 start가 팀 구성이 안되더라도 중간에 사이클이 만들어질 때 그 경우를 포함을 못 한다는 거다. 그래서 모든 노드에 대해서 다 dfs 탐색을 돌게 되고, 그 결과는 시간 복잡도 파파괴,,,

그래서 로직이 잘못된 건 아닌데 그냥 시간 초과나서 계속 틀렸다 껄껄껄,,,

그래서 그냥 돌면서 사이클 탐색까지 끝내려면 dfs의 로직을 바꿀 필요가 있다. 만약 방문한 적 없는 노드이면 dfs 탐색해주는 건 그대로 두는데, 만약 방문한 적 있고 얘 팀 관련된 판단이 아직 안내려졌다(그니까 팀에 속한 것도 아니고 안 속한 것도 아닌 상태)면 사이클이다. 그럼 그때부터 다시 자기로 돌아올 때까지 반복문 돌아주면서 팀 구성 완료라고 상태를 변경해주는 거다. ㅎㅎ

이렇게 코드를 바꿔보도록 하겠다…

// 텀 프로젝트 - 골드 3

#include <bits/stdc++.h>

using namespace std;

int n;
vector<int> team;
vector<int> visited;

int cnt = 0;
void dfs(int cur) {
    //방문만 한 상태로 설정, 판단 완료 : 2
    visited[cur] = 1;

    if (!visited[team[cur]]) dfs(team[cur]);
    // 방문은 했는데 아직 배정은 안 됨 -> 사이클
    else if (visited[team[cur]] == 1) {
        int t = team[cur];
        while (t != cur) {
            t = team[t];
            cnt++;
        }
        cnt++;
    }
    //판단 끝
    visited[cur] = 2;
}

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

    int t;
    cin >> t;

    while(t--) {
        cnt = 0;
        cin >> n;
        team.assign(n+1, 0);
        for (int i = 1; i <= n; i++) {
            cin >> team[i];
        }
        visited.assign(n+1, false);
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            if (visited[i]) continue;
            dfs(i);
        }
        cout << n-cnt << '\n';
    }
}

dfs를 도는 중 사이클을 만나면 거기서 바로 사이클 판단을 하도록 수정했다.

그리고 방문하면 바로 판단 끝으로 설정을 해서 방문했지만 판단이 안 된 케이스랑 판단이 된 케이스를 구분했다.

사이클 판단을 어떻게 효율적으로 할 수 있는지 알 수 있었던 교훈적인 문제였다~