[DFS/BFS] 백준 10451번 순열 사이클(Java)

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

10451번: 순열 사이클

📚 문제

1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면

와 같다. 또는, Figure 1과 같이 방향 그래프로 나타낼 수도 있다. 순열 그래프 (3, 2, 7, 8, 1, 4, 5, 6) 에는 총 3개의 사이클이 있다. 이러한 사이클을 "순열 사이클" 이라고 한다.

N개의 정수로 이루어진 순열이 주어졌을 때, 순열 사이클의 개수를 구하는 프로그램을 작성하시오.

예제 입력	예제 출력
2 8 3 2 7 8 1 4 5 6 10 2 1 3 4 5 6 7 9 10 8	3 7

 

📝 문제 해결

첫번째 줄을 인덱스, 두번째 줄을 배열의 값으로 생각해보자. 그러면 1번 인덱스는 3에 연결, 2번 인덱스는 2에 연결, 3번 인덱스는 7에 연결된 것을 확인할 수 있다.

1번 인덱스부터 순서대로 탐색한 뒤 이미 방문한 인덱스를 다시 방문하게 된다면 싸이클이 생기므로 그때 카운트를 세주면 된다.

 

 

💻 코드

• DFS (깊이 우선 탐색)

1. 탐색 시작 노드를 방문 처리를 한다. visited[index] = true
2. 해당 인덱스의 배열값에 아직 방문하지 않았다면 방문 처리를 하고 해당 인덱스의 배열값으로 다시 DFS 함수를 호출해준다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복하고 더 이상 수행할 수 없을 떄 카운트를 증가시켜준다.

import java.util.Scanner;

public class Main{
    static int[] graph;
    static boolean[] visited;
    
    public static void dfs(int index){
        visited[index] = true;
        if(!visited[graph[index]]) dfs(graph[index]);
    }
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        
        int T = sc.nextInt();
        for(int tc=0; tc<T; tc++){
            int N = sc.nextInt();
            
            int cnt = 0;
            graph = new int[N+1];
            visited = new boolean[N+1];
            
            for(int i=1; i<=N; i++) graph[i] = sc.nextInt();
            for(int i=1; i<=N; i++){
                if(!visited[i]){
                    dfs(i);
                    cnt++;
                }
            }
            System.out.println(cnt);
        }
    }
}

 

• BFS (너비 우선 탐색)

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
2. 큐에서 노드를 꺼내 해당 인덱스의 배열값에  방문하지 않았다면 방문 처리를 하고 해당 인덱스의 배열값을 큐에 삽입해준다.
3. 2번의 과정을 더 이상 수행할 수 없을 때 까지 반복하고 더 이상 수행할 수 없을 때 카운트를 증가시켜준다.

import java.util.*;

public class Main{
    static int cnt;
    static int[] graph;
    static boolean[] visited;
    
    public static void bfs(int index){
        Queue<Integer> que = new LinkedList<>(); 
        que.offer(index);
        visited[index] = true;
        
        while(!que.isEmpty()){
            int cur = que.poll();
            if(!visited[graph[cur]]){
                visited[graph[cur]] = true;
                que.offer(graph[cur]);
            }else{
                cnt++;
                break;
            }
        }
    }
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        
        int T = sc.nextInt();
        for(int tc=0; tc<T; tc++){
            int N = sc.nextInt();
            
            cnt = 0;
            graph = new int[N+1];
            visited = new boolean[N+1];
            
            for(int i=1; i<=N; i++) graph[i] = sc.nextInt();
            for(int i=1; i<=N; i++){
                if(!visited[i]){
                    bfs(i);
                }
            }
            System.out.println(cnt);
        }
    }
}