(6) [C++] 백준 No.9466 : 텀 프로젝트

문제

풀이

자세한 풀이 : https://ldgeao99.tistory.com/398

# C++(재귀적 구현)

#include<iostream>
#include<cstring>
using namespace std;

int arr[100001];          // 인접리스트
int check[100001];        // 방문유무 및 방문순서를 저장하는 check 배열
int which_search[100001]; // 몇번째로 진행되는 탐색의 경로에 포함되는지 저장하는 배열

// 함수가 한번 호출되면 이미 방문한 정점을 찾을 때 까지 진행됨 => 이것이 가능한 이유는 모든 정점이 다음 정점을 가지기 때문에 가능함.
int dfs(int node, int cnt, int &step)
{
    // 이미 방문한 곳을 재방문하려고 한다면 이것이 사이클인지 확인해줘야 함
    if (check[node] != 0){
        if(which_search[node] != step)
            return 0;
        else
            return cnt - check[node];
    }
    // 첫 방문이라면 방문순서 및 몇번째로 진행되는 탐색인지 기록, 후 다음정점 탐색 진행
    else{
        check[node] = cnt;
        which_search[node] = step;
        int next = arr[node];
        return dfs(next, cnt+1, step);
    }
}

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

    int t;
    cin >> t;

    while(t--){
        // 데이터 입력받기 및 초기화
        int n;
        cin >> n;

        for(int i = 1; i <= n; i++)
            cin >> arr[i];

        memset(check, 0, sizeof(check));
        memset(which_search, 0, sizeof(which_search));

        // 시작점을 바꿔가며 탐색을 진행하면서 발견되는 사이클의 크기를 합함
        int ans = 0;

        for (int i = 1; i <= n; i++ )
            ans += dfs(i, 1, i);

        // 결과 = 총 학생수 - 팀을 이룬 학생수
        cout << n-ans << "\n";
    }
}

# C++(비재귀적 구현)

#include<iostream>
#include<cstring>
using namespace std;

int arr[100001];          // 인접리스트
int check[100001];        // 방문유무 및 방문순서를 저장하는 check 배열
int which_search[100001]; // 몇번째로 진행되는 탐색의 경로에 포함되는지 저장하는 배열

// 함수가 한번 호출되면 이미 방문한 정점을 찾을 때 까지 진행됨 => 이것이 가능한 이유는 모든 정점이 다음 정점을 가지기 때문에 가능함.
int dfs(int node, int cnt, int &step)
{
    while(check[node] == 0){
        check[node] = cnt;
        which_search[node] = step;
        cnt += 1;
        node = arr[node];
    }

    if (step == which_search[node])
        return cnt - check[node];

    return 0;
}

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

    int t;
    cin >> t;

    while(t--){
        // 데이터 입력받기 및 초기화
        int n;
        cin >> n;

        for(int i = 1; i <= n; i++)
            cin >> arr[i];

        memset(check, 0, sizeof(check));
        memset(which_search, 0, sizeof(which_search));

        // 시작점을 바꿔가며 탐색을 진행하면서 발견되는 사이클의 크기를 합함
        int ans = 0;

        for (int i = 1; i <= n; i++ )
            ans += dfs(i, 1, i);

        // 결과 = 총 학생수 - 팀을 이룬 학생수
        cout << n-ans << "\n";
    }
}

 

# C++(재귀적 구현, cnt 1부터 쭉 증가시키기)

#include<iostream>
#include<cstring>
using namespace std;

int arr[100001];          // 인접리스트
int check[100001];        // 방문유무 및 방문순서를 저장하는 check 배열
int which_search[100001]; // 몇번째로 진행되는 탐색의 경로에 포함되는지 저장하는 배열

// 함수가 한번 호출되면 이미 방문한 정점을 찾을 때 까지 진행됨 => 이것이 가능한 이유는 모든 정점이 다음 정점을 가지기 때문에 가능함.
int dfs(int node, int &cnt, int &step)
{
    // 이미 방문한 곳을 재방문하려고 한다면 이것이 사이클인지 확인해줘야 함
    if (check[node] != 0){
        if(which_search[node] != step)
            return 0;
        else
            return cnt - check[node];
    }
    // 첫 방문이라면 방문순서 및 몇번째로 진행되는 탐색인지 기록, 후 다음정점 탐색 진행
    else{
        check[node] = cnt;
        which_search[node] = step;
        int next = arr[node];
        cnt += 1;
        return dfs(next, cnt, step);
    }
}

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

    int t;
    cin >> t;

    while(t--){
        // 데이터 입력받기 및 초기화
        int n;
        cin >> n;

        for(int i = 1; i <= n; i++)
            cin >> arr[i];

        memset(check, 0, sizeof(check));
        memset(which_search, 0, sizeof(which_search));

        // 시작점을 바꿔가며 탐색을 진행하면서 발견되는 사이클의 크기를 합함
        int ans = 0;

        int cnt = 1;

        for (int i = 1; i <= n; i++ )
            ans += dfs(i, cnt, i);

        // 결과 = 총 학생수 - 팀을 이룬 학생수
        cout << n-ans << "\n";
    }
}