[백준 9466] 텀 프로젝트

0. 제목

• 백준 9466 텀 프로젝트
• BOJ 9466 텀 프로젝트
• C++ 9466 텀 프로젝트

---

1. 문제

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

---

2. 풀이

• 문제에서 프로젝트를 함께 하고 싶은 학생을 단 한 명만 선택할 수 있다고 하였다.
• 그렇기 때문에 vector를 이용할 필요가 없고 connect라는 배열을 선언해서 해결이 가능하다.
• connect[2] = 3; 의 의미는 2번 학생이 3번 학생을 가리키고 있다는 것이다.
• done은 이미 방문하였고 더 이상 볼 필요가 없는 점들을 표시하는 배열이다.
• visited는 방문 여부를 체크하는 배열이다.
• 먼저 여기서 dfs 함수는 사이클을 체크하는 함수로 쓰인다. 이 함수에 대해 설명해보면 다음과 같다.
• 처음에 방문하므로 visited[x] = true 이고 y는 x에 연결된 학생번호를 가리킨다.
• 만약 연결된 학생이 방문하지 않은 점이었다면 재귀적으로 다시 dfs(y)를 한다. 하지만, 방문했을 경우 사이클체크가 완료되었는지 확인한다.
• 사이클 즉, done배열에 포함이 되어 있지 않으면 그 연결된 점부터 자기 자신으로 돌아오기 하나 전까지 반복하면서 개수를 센다.
• 반복문이 완료되면 자기 자신도 포함 시켜야 하므로 개수에 1을 더해준다.
• 모든 루프에서 조건문이 끝나면 done[x] = true; 즉, 더이상 볼 필요 없는 배열의 값에 true를 넣어준다.
• 1->2->3->1  이 사이클로 예를 들어보면, 1에서 시작하면 dfs(1)을 수행한다. visited[1] = true 가 되고 y는 2가 된다. 2는 방문한적없으니 dfs(2)를 한다. 똑같이 visited[2] = true가 되고 y = 3이 된다. dfs(3)을 실시한다. visited[3] = true가 되고 y = 1 이 된다.
• y는 이미 방문 한 배열이므로 else구문을 실행하게 된다. done[1] = false 이며 for 문을 살펴보면 다음과 같다.
• for(i = 1; i != 3; i = connect[i])   이것은 i = 1 부터 연결된 점을 따라가다가 3이 되면 탈출하는 것이다. 연결된 점을 따라가면서 개수를 세고 반복문을 탈출하게 되면 i==3 일때 개수를 안세주었기 때문에 개수에 1을 더해준다.
• 그 후 done[3] = true를 하고 재귀를 사용했으므로 나머지 done[2] = true , done[1] = true를 해준다.
• main함수를 보면 매번 케이스마다 배열 3개를 0과 false로 초기화해준다. 그리고 1부터 n까지 반복하면서 방문하지 않은 점이라면 그 점부터 dfs를 실시한다.
• 그렇게 센 개수들을 모든 점의 개수인 n에서 뺀다. 그럼 어느 프로젝트 팀에도 속하지 않는 학생들의 수가 나온다.

---

3. 코드

#include <iostream>
#include <cstring>
using namespace std;
 
int connect[100001];//화살표가 한방향으로 가기때문에 vector대신 배열 사용가능
bool done[100001];
bool visited[100001];
int T, n, cnt;
 
void dfs(int x){
    visited[x] = true;
    int y = connect[x];
    if(!visited[y])
        dfs(y);
    else{
        if(!done[y]){
            for(int i = y; i != x; i = connect[i]){//
                cnt++;//연결된 점들 개수 세기
            }
            cnt++;//자기 자신
        }
    }
    done[x] = true;
}
 
int main(int argc, const char * argv[]) {
    cin >> T;
    for(int i = 0; i < T; i++){
        cin >> n;
        
        cnt = 0;
        memset(connect, 0, sizeof(connect));
        memset(done, false, sizeof(done));
        memset(visited, false, sizeof(visited));
        
        for(int j = 1; j <= n; j++){
            cin >> connect[j];
        }
        for(int j = 1; j <= n; j++){
            if(!visited[j])
                dfs(j);
        }
        
        cout << n - cnt << '\n';
    }
    return 0;
}