[백준(BOJ)] 9466번: 텀 프로젝트 (DFS/BFS, C++)

📝 문제풀이 과정

---

visited: 방문여부 체크

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

1(current)이 3(next)을 지목했지만, 3(current)에서 3(next)을 지목했기 때문에 3 혼자서만 팀이고 1은 팀이 되지 못한다.

 

반례

6
2 3 4 5 6 2
output : 1

5
2 5 4 5 2
output : 3

6
1 3 4 3 2 6
output : 2

13
2 4 5 2 4 1 8 9 10 11 9 10 10
output : 8

10
2 5 7 1 6 8 8 3 5 10
output : 6

10
2 7 10 5 3 3 9 10 6 3
output : 8

6
2 1 1 2 6 3
output : 4

#include <stdio.h>
#include <deque>
#include <queue>
using namespace std;

void DFS(int start, deque<int> *graph, bool *visited, bool *done, int *count){
    visited[start] = true;
    printf("[+] %d visited\n", start);
    int next = graph[start][0];
    if(visited[next] == false){
        DFS(next, graph, visited, done, count);
    }
    // count that included in project
    else if(!done[next]){
        for(int i=next; i !=start; i=graph[i][0]) { (*count)++; printf("%d counted.\n", i); } 
        (*count)++; // for counting start
        printf("%d counted.\n", start);
    }

    done[start] = true;
}

int main(){
    int T; // T: # of testcase
    scanf("%d", &T);

    for(int i=0; i<T; i++){
        int n;
        int count=0; // n: # of students
        scanf("%d", &n);
        deque<int> graph[n+1];
        bool visited[n+1];
        bool done[n+1];
        fill(visited, visited+n+1, false);
        fill(done, done+n+1, false);

        for(int j=1; j<=n; j++){
            int num; 
            scanf("%d", &num);
            graph[j].push_back(num);
        }
        
        for(int j=1; j<=n; j++){
            if(visited[j] == false) DFS(j, graph, visited, done, &count);
        }
        
        printf("%d\n", n-count);
    }
}

각 graph[i]는 하나씩만 원소를 가지므로, start에서 next는 항상 graph[start][0]이 된다.

이것으로 시간복잡도를 줄여서 시간초과 문제를 해결한다.

또한 visited일 때, 방문이 끝나지 않았으면 해당 visited부터 graph[i][0]에 대해 count++을 해서 프로젝트에 속한 것을 체크하고, start와 같다면 끝낸다. 반복문이 끝나면 start에 대한 count도 한다.

만약 start = 6이고 다시 next = 4라면 이미 visited이므로 반복문을 시작해서 4부터 카운팅을 하고,

i=4, i=graph[4]=7, i=graph[7]=6으로 다시 start로 돌아오면 끝낸다. 이때 6에 대한 카운팅도 해야 하므로 반복문 끝나고 한번 더 카운팅을 해준다.

그리고 start에 대해 done[start]=true로 방문이 끝나고 더이상 방문할 일이 없음을 표시한다.

 

 

 

💻 C++ 제출코드

---

#include <bits/stdc++.h>
using namespace std;

void DFS(int start, int *graph, bool *visited, bool *done, int *count){
    visited[start] = true;
    int next = graph[start];
    if(visited[next] == false) DFS(next, graph, visited, done, count);
    // count that included in project
    else if(!done[next]){
        for(int i=next; i !=start; i=graph[i])(*count)++; 
        (*count)++; // for counting start
    }
    done[start] = true;
}

int main(){
    int T; // T: # of testcase
    scanf("%d", &T);

    for(int i=0; i<T; i++){
        int n;
        int count=0; // n: # of students
        scanf("%d", &n);
        int graph[n+1]={0,};
        bool visited[n+1];
        bool done[n+1];
        fill(visited, visited+n+1, false);
        fill(done, done+n+1, false);

        for(int j=1; j<=n; j++) scanf("%d", &graph[j]);
        
        for(int j=1; j<=n; j++){
            if(visited[j] == false) DFS(j, graph, visited, done, &count);
        }
        printf("%d\n", n-count);
    }
}

문제풀이 과정에서는 STL로 구현을 했었는데, 시간초과 문제가 해결되지 않아서 그냥 deque 같은 STL 안 쓰고 배열로 graph 만들고 입력받으니까 시간초과 문제를 해결하고 맞았습니다를 받을 수 있었다.

n-count는 count가 프로젝트에 속한 사람 수이므로 n-count로 프로젝트에 속하지 않은 수로 답을 구한다.

 

 

👏 결과

---