(4) [C++, Java] 백준 No.10451 : 순열 사이클

문제

풀이

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

# C++(dfs탐색을 재귀 구현으로 푼것)

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

int arr[1001];      // 인접 리스트
bool check[1001];   // 인접 리스트
void dfs(int node);

int main()
{
    int t;
    cin >> t;

    while(t--){
        int v;
        cin >> v;

        // 정보를 입력받아 원소가 1개인 인접 리스트 생성
        for (int i = 1; i <= v; i++){
            int a;
            cin >> a;
            arr[i] = a;
        }

        // 다음 테스트 케이스를 위한 초기화
        memset(check, false, sizeof(check));

        // 탐색이 진행된 횟수 카운트
        int ans = 0;
        for (int i = 1; i <= v; i++){
            if (check[i] == false){
                ans += 1;
                dfs(i);
            }
        }

        // 결과출력
        cout << ans << "\n";
    }
}

void dfs(int node){
    check[node] = true;
    //cout << node << "";
    int next = arr[node];
    if (check[next] == false){
        dfs(next);
    }
}

# C++(dfs탐색을 비재귀 구현으로 푼것)

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

int arr[1001];      // 인접 리스트
bool check[1001];   // 인접 리스트

int main()
{
    int t;
    cin >> t;

    while(t--){
        int v;
        cin >> v;

        // 정보를 입력받아 원소가 1개인 인접 리스트 생성
        for (int i = 1; i <= v; i++){
            int a;
            cin >> a;
            arr[i] = a;
        }

        // 다음 테스트 케이스를 위한 초기화
        memset(check, false, sizeof(check));

        // 탐색이 진행된 횟수 카운트
        int ans = 0;
        for (int i = 1; i <= v; i++){
            if (check[i] == false){
                ans += 1;
                // DFS탐색
                int node = i;
                while(check[node] == false){
                    check[node] = true;
                    node = arr[node];
                }
            }
        }

        // 결과출력
        cout << ans << "\n";
    }
}

# Java

import java.util.*;

public class Main {
    public static void dfs(int[] a, boolean[] c, int x) {
        if (c[x]) return;
        c[x] = true;
        dfs(a, c, a[x]);
    }
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            int n = sc.nextInt();
            int[] a = new int[n+1];
            boolean[] c = new boolean[n+1];
            for (int i=1; i<=n; i++) {
                a[i] = sc.nextInt();
                c[i] = false;
            }
            int ans = 0;
            for (int i=1; i<=n; i++) {
                if (c[i] == false) {
                    dfs(a, c, i);
                    ans += 1;
                }
            }
            System.out.println(ans);
        }

    }
}