[문제 풀이] 백준 11724번 연결 요소의 개수JAVA

문제

 

  문제접근 방법   

해당 문제는 방향 없는 그래프가 주어졌을 때 연결 요소의 개수를 구하는 프로그램을 작성하는 문제로

전형적인 인접리스트를 활용해 탐색하는 문제라고 생각된다. 문제에서 주어진 정점과 연결 관계가 몇 덩어리 나오냐를 구하는 것으로 위의 예시에서 1,2,5가 한 덩어리 3,4,6이 한 덩어리 인 것을 확인해 볼 수 있고 개수 2인 것을 확인하였다.

문제를 dfs/bfs 어떤 방법이든지 풀이 가능하지만 먼저 dfs를 통해 문제를 해결해보도록 하겠다.  

 

< 최종 코드 >

import java.util.*;

public class Main{
    public static boolean visited[];
    public static ArrayList<ArrayList<Boolean>> list=new ArrayList<>();
    public static void main(String args[]){
        Scanner s=new Scanner(System.in);
        
        int n=s.nextInt();
        int m=s.nextInt();
        int cnt=0;
        visited=new boolean[n];
        for(int i=0;i<n;i++){
            list.add(new ArrayList());
            for(int j=0;j<n;j++){
                list.get(i).add(false);
            }
        }
        for(int i=0;i<m;i++){
            int a=s.nextInt();
            int b=s.nextInt();
            list.get(a-1).set(b-1,true);
            list.get(b-1).set(a-1,true);
        }

        for(int i=0;i<n;i++){
            if(!visited[i]){
                dfs(i);
                cnt++;
            }
        }
        System.out.println(cnt);
        
    }
    
    public static void dfs(int start){
        if(visited[start])return;
        visited[start]=true;
        for(int i=0;i<visited.length;i++){
            if(list.get(start).get(i)){
                dfs(i);
                
            }
        }
    }
}

위에서 언급하였듯이 인접리스트를 통해 각 값들을 저장하고 이후 dfs에서 방문했다면 종료하고 방문하지 않았다면  재귀함수를 통해 해당 정점으로 이동하는 방식으로 작성하였다.  연결요소를 카운트하는 방식은 dfs가 호출될 때마다 카운트해 주는 방식으로 코드를 완성하였다. 

 

  마무리  

해당 문제는 인접리스트를 활용한 기본적인 문제로 나중에도 인접리스트는 활용할 부분이 많아 꼭 익히고 가면 좋겠다고 생각한다.

  추가 코드 분석 및 풀이  

해당 문제도 BFS로 접근이 가능하기 떄문에 아래와 같이 풀이해 보았다.

 

< 추가 코드 ver BFS >

- 추후 업데이트 예정