[문제 풀이] 백준 10451번 순열 사이클 JAVA

문제

 

  문제접근 방법   

해당 문제는 N을 입력받았을 때  1~N까지의 수와 따로 입력 받은 N개의 순열과 각각 간선을 이어 그래프를 만들 수 있다.

이때 순열 사이클의 수를 구하는 프로그램을 작성하는 문제이다. 

예를 들어 

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

1에서 3으로 연결 2에서 2로 연결 3에서 7로 연결 이런식으로 문제를 접근하는 것이다.

문제를 읽고 해당 문제는 인접리스트를 통해 입력받은 값을 저장하고 연결되어 있는 그래프의 수만 카운트하면 되겠다고 생각했다.

 

< 최종 코드 >

import java.util.*;

public class Main{
    public static boolean visited[];
    
    public static List<ArrayList<Integer>> list;
    public static void main(String args[]){
        Scanner s=new Scanner(System.in);
        StringBuilder sb=new StringBuilder();
        
        int test=s.nextInt();
        for(int t=0;t<test;t++){
            int n=s.nextInt();
            int num[]=new int[n+1];
            int count=0;
            visited=new boolean[n+1];
            list=new LinkedList<>();
            for(int i=0;i<=n;i++){
                if(i!=0)num[i]=s.nextInt();
                list.add(new ArrayList<>());
            }
            for(int i=1;i<=n;i++){
                list.get(i).add(num[i]);
            }
            for(int i=1;i<=n;i++){
                if(!visited[i]){
                    bfs(i);
                    count++;
                }
            }
            sb.append(count).append("\n");
        }
        System.out.print(sb);
    }
    public static void bfs(int i){
        Queue<Integer>q=new LinkedList<>();
        q.offer(i);
        visited[i]=true;
        while(!q.isEmpty()){
            int number=q.poll();
            for(int k=0;k<list.get(number).size();k++){
                if(!visited[list.get(number).get(k)]){
                    visited[list.get(number).get(k)]=true;
                    q.offer(list.get(number).get(k));
                }
            }
        }
    }
}

해당 코드 또한 앞서 풀이했던 바이러스 문제와 굉장히 유사하다. 

인접리스트를 선언하여 입력받은 순열과 1~N개의 수의 간선 관계를 저장하고 이를 bfs에서 Queue를 통해 정점 번호만 저장해 둔 후 연결된 간선을 통해 또 다른 정점 번호를 저장하는 것을 반복해 하나의 그래프를 확인 이를 반복 카운트하면 몇 개의 순열 그래프가 완성되는지 간단하게 구할 수가 있다.

 

  마무리  

해당 문제는 인접 리스트에대해서 다시 한번 떠올리고 복습할 수 있는 기회여서 좋은 문제였다. 문제에서 어려웠던 부분은 풀이를 떠올리는 것보다 i에서 ㅠ i로 간선을 이어 그래프를 만들 수 있다는 부분이 처음에는 이해가 가지 않았지만 그림을 통해 이해해 문제를 풀 수 있었다.

 

  추가 코드 분석 및 풀이  

해당 문제도 다른 문제들과 같이 DFS로도 풀이가 가능하다.

 

< 추가 코드 ver DFS >

- 추후 업데이트 예정