백준 9466번 [텀 프로젝트](C++) -yes6686- 티스토리

 

백준 문제 풀이: 9466 (텀 프로젝트)

---

문제 링크: https://www.acmicpc.net/problem/9466

문제 설명:

N명의 학생들이 각각 한 명씩만 선택하여 사이클을 이루는 구조에서, 팀을 이룰 수 있는 사람들의 수를 파악하는 문제입니다.
선택 관계는 방향 그래프로 표현되며, 사이클을 이루는 사람만이 팀이 됩니다. 팀을 이룰 수 없는 학생의 수를 출력해야 합니다.

---

문제 해결 코드

// 백준 9466 - 텀 프로젝트
#include <iostream>
#include <vector>
#include <queue>
#include <string.h>
using namespace std;

vector<int> v[100001];
queue<int> q;
int visited[100001];
int checked[100001];

void dfs(int s, int x, int d) {
    int k = v[x][0];  // x가 선택한 학생
    if (checked[k] == -1 || checked[k] == 1) {
        while (!q.empty()) {
            checked[q.front()] = -1;
            q.pop();
        }
        return;
    }

    if (visited[k]) {
        int flag = 0;
        while (!q.empty()) {
            int cur = q.front(); q.pop();
            if (cur == k) flag = 1;
            checked[cur] = (flag ? 1 : -1);
        }
        return;
    }

    visited[k] = 1;
    q.push(k);
    dfs(s, k, d + 1);
}

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

    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++) {
            int x;
            cin >> x;
            v[i].push_back(x);
        }

        for (int i = 1; i <= n; i++) {
            if (!visited[i]) {
                visited[i] = 1;
                q.push(i);
                dfs(i, i, 0);
            }
        }

        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            if (checked[i] == -1) cnt++;
            v[i].clear();
        }

        cout << cnt << '\n';
        memset(visited, 0, sizeof(visited));
        memset(checked, 0, sizeof(checked));
    }
}

---

코드 설명

DFS를 사용하여 각 학생이 이루는 선택 관계를 따라가며 사이클을 탐지합니다.

• 핵심 알고리즘: DFS를 통한 사이클 탐지 (Graph Cycle Detection). 사이클에 포함된 노드만 팀으로 인정합니다.
• 구현 세부사항:
  • visited: 현재 DFS 경로에서 방문 여부
  • checked: -1이면 팀 X, 1이면 팀 O
  • 큐 q: 경로를 기록하고, 사이클인지 아닌지에 따라 분기처리
• 시간 복잡도 분석: 각 노드는 한 번만 DFS에 포함되므로 O(n)입니다.

---

결과

예제 입력:

2
7
3 1 3 7 3 4 6
8
1 2 3 4 5 6 7 8

예제 출력:

3
0

사이클을 이루지 못한 학생의 수를 출력합니다.

그래프 탐색에서 방문 처리 순서와 큐의 활용이 중요한 문제입니다. 다른 방식이나 개선 아이디어가 있다면 댓글로 자유롭게 의견 남겨주세요!