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

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

 

 

이 문제는 N명이 학생이 주어지고 N명의 학생들이 원하는 학생과 팀이 되기 위해서 다른사람을 택하는 번호가 주어질때

택한사람들 끼리 사이클을 이루거나 자기 자신을 택할경우 팀이 만들어져 팀이 안만들어지는 사람들의 수를 출력하는 문제이다.

 

 

위 예시처럼 서로가 서로를 선택해서 물고무는 사이클 관계일 경우 팀이 성립하는데 이러한 사이클 형태를 알기 위해서

dfs(깊이 우선 탐색)을 활용하였다.

그 이유는 bfs를 사용할 경우 사이클을 판별하기 힘들어 따로 사이클 배열을 만들어서 방문했지만 사이클 배열에 사용되지 않았을 경우 이는 사이클 형태라고 판단하였다.

 

정답코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    int y;
    int r;
};

int dx[] = {-1, 1, 0, 0, 1, -1, -1, 1};
int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
int N, answer, T;
int arr[100001];
bool visited[100001];
bool cycle[100001];

void dfs(int Node) {
    visited[Node] = true;
    int nextNode = arr[Node];

    if(!visited[nextNode]) {
        dfs(nextNode);
    }
    else if(!cycle[nextNode]) {
        for(int i = nextNode; i != Node; i = arr[i]) {
            answer++;
        }
        answer++;
    }
    cycle[Node] = true;
}

void solve() {
    for(int i = 1; i <= N; i++) {
        if(!visited[i]) {
            dfs(i);
        }
    }

    cout << N - answer << endl;
}

void input() {
    cin >> T;

    while(T--) {
        cin >> N;

        for(int i = 1; i <= N; i++) {
            cin >> arr[i];
        }

        solve();
        memset(visited, 0, sizeof(visited));
        memset(cycle, 0, sizeof(cycle));
        answer = 0;
    }
}

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

    input();
}

 

가장 핵심인 dfs함수를 살펴보면

void dfs(int Node) {
    visited[Node] = true;
    int nextNode = arr[Node];

    if(!visited[nextNode]) {
        dfs(nextNode);
    }
    else if(!cycle[nextNode]) {
        for(int i = nextNode; i != Node; i = arr[i]) {
            answer++;
        }
        answer++;
    }
    cycle[Node] = true;
}

 

현재 노드에서 부터 탐색할때 다음으로 선택한 노드에 방문하지 않았다면 계속 다음사람을 호출한다

 

이때 방문했으며 사이클 노드에 체크되지 않은 경우 이는 사이클을 이루기 때문에 배열에 그 값을 변경시켜 값을 증가시킨다 이때 사이클 노드와 같을 경우 탈출하여 사이클 노드를 방문체크한다.