[백준] 11724번 - 연결 요소의 개수

 

11724번: 연결 요소의 개수

 

 

문제에 풀이에 앞서 그래프에 대한 정리가 잘 되어 있는 글을 저장해 두겠다.

[Algorithm] 자료구조 그래프(Graph)란 무엇인가?

 

 

 

i) 방향이 없는 그래프

ii) 깊이 우선탐색과 너비 우선 탐색

 

복잡한 알고리즘 없이 그래프와 탐색 방식들에 대해 가볍게 연습해 볼 수 있는 문제이다. 문제도 아주 짧고 간결하다.

 

문제가 요구하는 것은 연결 요소의 개수이다. 한 번 방문한 노드를 방문처리하면서 하나의 연결 요소를 완전 탐색할 때 count++ 해주면 된다.

 

dfs와 bfs를 연습해보기 위해 두 가지를 모두 사용하여 문제를 해결 하였다. 보통 dfs로 해결하는 경우 메모리 사용이 더 큰 경향이 있는데 이 문제 한해서는 성능차이가 크게 나지 않았다.

 

간선에 대한 정보를 저장하는 방식은 이중 배열을 사용하는 방식과 리스트를 사용하는 방식이 있는데, 다른 모든 노드와의 간선이 존재하는지 체크하는게 왠지 모르게 불필요한 작업 같아서 나는 리스트 사용을 선호하는 편이다.

 

 

 

DFS (Depth First Search) 사용

재귀함수를 사용할 때에는 종료조건을 명시해 주어야 재귀를 벗어나지 못하고 무한 루프에 빠지는 것을 막을 수 있지만 방문 체크를 해서 방문을 하지 않은 노드에 대해서만 탐색하도록 하여 종료조건을 빼주었다. 그래도 웬만해서는 종료조건을 넣어주는 것이 좋을 듯 하다. 

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

public class Main {
    
    static ArrayList<Integer>[] link;
    static boolean[] visited;
    static int N, M;
    
    public static void main (String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        
        int count = 0;
        
        st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        link = new ArrayList[N+1];
        visited = new boolean[N+1];
        
        for (int i=1; i<N+1; i++) link[i] = new ArrayList<>();
        
        for (int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            
            link[u].add(v);
            link[v].add(u);
        }
        
        for (int i=1; i<=N; i++) {
            if (visited[i] == false) { 
                dfs(i);
                count++;
            }
        }
        
        System.out.println(count);
        
        br.close();
    }
    
    static void dfs (int node) {
        
        visited[node] = true;
        
        for (int num : link[node]) 
            if (visited[num] == false) dfs(num);
    }
}

 

BFS (Breadth First Search) 사용

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

public class Main {
    
    static Queue<Integer> que;
    static ArrayList<Integer>[] link;
    static boolean[] visited;
    static int N, M;
    
    public static void main (String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        que = new LinkedList<>();
        StringTokenizer st = null;
        
        int count = 0;
        
        st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        link = new ArrayList[N+1];
        visited = new boolean[N+1];
        
        for (int i=1; i<N+1; i++) link[i] = new ArrayList<>();
        
        for (int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            
            link[u].add(v);
            link[v].add(u);
        }
        
        for (int i=1; i<=N; i++) {
            if (visited[i] == false) { 
                bfs(i);
                count++;
            }
        }
        
        System.out.println(count);
        
        br.close();
    }
    
    static void bfs (int node) {
        
    	visited[node] = true;
        que.offer(node);
        
        while (!que.isEmpty()) {
            
            int n = que.poll();
            
            for (int next : link[n]) {
                if (visited[next] == false) {
                    visited[next] = true;
                    que.offer(next);
                }
            }
        }
    }
}