[Silver III/JAVA] 10451 순열 사이클

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

 

 

• DFS, BFS 두 가지로 풀 수 있는 문제
• 시간복잡도는 O(N)으로 DFS, BFS 동일하다.

 

DFS (깊이우선탐색) 풀이

 

• 문제를 보면 순열을 1부터 세기 때문에 배열의 크기 설정에 주의한다.
• 입력받은 순열을 배열에 넣을 때도 ArrayIndexOutOfBoundsException가 발생하지 않도록 주의한다.
• 순열 배열에 인덱스 1부터 값을 넣기 때문에 그 값에 해당하는 str 배열에서는 index-1을 해줘야한다.
• 노드 방문을 기록할 boolean 타입의 visited 배열을 만들어서 사이클이 중복으로 체크되지 않도록 탐색한다.

[ 탐색 과정 ]

 

* n = 1

dfs(1)

visited[1] = true

nextNode = 3

 

dfs(3) 

visited[3] = true

nextNode = 7

 

dfs(7)

visited[7] = true

nextNode = 5

 

dfs(5)

visited[5] = true

nextNode = 1

-> visited[1] = true 이므로 탐색 종료하고 cycle을 카운트한다.

 

첫번째 탐색이 끝나면 visited 배열은 아래와 같은 상태가 될 것이다.

1	2	3	4	5	6	7	8
true	false	true	false	true	false	true	false

 

• 이런식으로 dfs 재귀함수를 실행하고 탐색이 한 번 완료되면 순열 사이클을 카운트한다.

import java.io.*;
import java.util.*;

public class Main{
    static boolean[] visited;
    static int[] arr;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //테스트 케이스 개수 입력
        int T = Integer.parseInt(br.readLine());
        
        for(int i=0; i<T; i++){
            //순열크기 입력
            int N = Integer.parseInt(br.readLine());
            arr = new int[N+1];
            
            //노드 방문 기록할 배열
            visited = new boolean[N+1];
            
            //순열 입력
            String[] str = br.readLine().split(" ");           
            for(int j=1; j<=N; j++){
                arr[j] = Integer.parseInt(str[j-1]);
            } 
            
            int cycle = 0;
            
            //탐색
            for(int n=1; n<=N; n++){
                if(!visited[n]){ //방문하지 않은 노드에서 시작
                    dfs(n);
                    cycle++;
                }                
            }
            
            System.out.println(cycle);
        }
    }
    
    //DFS
    static void dfs(int node){
        //현재 노드 방문
        visited[node] = true;
        int nextNode = arr[node];
        if(!visited[nextNode]){ //다음 노드 방문안했으면 탐색
            dfs(nextNode);
        }
    }
}

 

 

BFS (너비우선탐색) 풀이

 

• 전체적인 코드는 DFS와 똑같고 탐색하는 부분만 차이가 있다.
• Queue를 사용하여 각 레벨의 노드를 순차적으로 탐색한다.
• 이 문제를 기준으로 봤을 때 개인적으로 DFS 알고리즘을 사용하는 것이 좀 더 간단하다고 느꼈다.
• Queue에서 poll()은 현재값을 리턴, 비어있으면 null을 리턴한다.

 

import java.io.*;
import java.util.*;

public class Main{
    static boolean[] visited;
    static int[] arr;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //테스트 케이스 개수 입력
        int T = Integer.parseInt(br.readLine());
        
        for(int i=0; i<T; i++){
            //순열크기 입력
            int N = Integer.parseInt(br.readLine());
            arr = new int[N+1];
            
            //노드 방문 기록할 배열
            visited = new boolean[N+1];
            
            //순열 입력
            String[] str = br.readLine().split(" ");           
            for(int j=1; j<=N; j++){
                arr[j] = Integer.parseInt(str[j-1]);
            } 
            
            int cycle = 0;
            
            //탐색
            for(int n=1; n<=N; n++){
                if(!visited[n]){ //방문하지 않은 노드에서 시작
                    bfs(n);
                    cycle++;
                }                
            }
            
            System.out.println(cycle);
        }
    }
    
    //BFS
    static void bfs(int start){
        //Queue 생성
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        visited[start] = true;
        
        while(!queue.isEmpty()){
            int current = queue.poll(); //현재 노드
            int nextNode = arr[current]; //순열에 따른 이동
            
            if(!visited[nextNode]){
                visited[nextNode] = true;
                queue.add(nextNode);
            }
        }
    }
}