[백준] Silver II. 연결 요소의 개수

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

 

 

사용 알고리즘

• BFS
• DFS
• 그래프 탐색

풀이

BFS

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.*;

public class Main {
    static int n, m;
    static List<List<Integer>> graph = new ArrayList<>();
    static boolean [] visited;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        visited = new boolean[n + 1];
        for(int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            graph.get(u).add(v);
            graph.get(v).add(u);
        }

        int res = 0;
        for(int i = 1; i <= n; i++){
            if (visited[i]) continue;
            Queue<Integer> queue = new LinkedList<>();
            queue.add(i);
            visited[i] = true;

            while (!queue.isEmpty()) {
                int v = queue.poll();
                for(int next : graph.get(v)) {
                    if (!visited[next]) {
                        queue.add(next);
                        visited[next] = true;
                    }
                }
            }
            res++;
        }
        System.out.println(res);
    }
}

 

DFS

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.*;

public class Main {
    static int n, m;
    static List<List<Integer>> graph = new ArrayList<>();
    static boolean [] visited;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        visited = new boolean[n + 1];
        for(int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            graph.get(u).add(v);
            graph.get(v).add(u);
        }

        int count = 0;
        for(int i = 1; i <= n; i++) {
            if (!visited[i]) {
                dfs(i);
                count++;
            }
        }
        System.out.println(count);
    }

    public static void dfs(int node) {
        visited[node] = true;
        for(int num : graph.get(node)) {
            if (!visited[num]) {
                dfs(num);
            }
        }
    }
}

 

회고

 

그래프 문제는 일단 인접 행렬 vs 인접 리스트로 접근할 수 있다. 

 

두 정점 사이의 간선이 1개 이하일 때, 설명을 해보려고 한다.

 

인접 행렬은, 쉽게 이야기 해서 2차원 배열로 문제를 접근할 수 있다.

출처: 바킹독 블로그

static int[][] graph;
for (int i = 0; i < m; i++) {
    st = new StringTokenizer(br.readLine());
    int u = Integer.parseInt(st.nextToken());
    int v = Integer.parseInt(st.nextToken());
    graph[u][v] = 1;
    graph[v][u] = 1;
}

 

이런식으로 인접 행렬에 간선 정보를 받아서 저장해준다. 

 

2차원 배열로 선언하므로 공간 복잡도는 O(V^2) 이고, 시간 복잡도는 최악의 케이스일때도 O(V)에 커버가 가능하다.

 

인접 리스트는, 

출처: 바킹독 블로그

 

 

이런식으로 V개의 리스트만을 만들어서 연결된 정점을 넣으면 된다.

static List<List<Integer>> graph = new ArrayList<>();
public static void main(String[] args) throws IOException {
    for (int i = 0; i <= n; i++) {
        graph.add(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());
        graph.get(u).add(v);
        graph.get(v).add(u);
    }
	...
}

 

문제에서 주어진 N(정점의 개수)만큼 리스트를 초기화 해주고, 간선 정보를 저장해 준다.

 

공간복잡도는 LinkedList 형태 (chain같이 이어지는 형식) 이므로 O(V+E)이고, 시간 복잡도도 O(V+E)이다.

 

인접 리스트는 간선의 수가 적은 그래프에서 더 효율적으로 시간복잡도를 줄일 수 있다.

 

출처: 바킹독 블로그

 

BFS와 DFS는 다차원 배열에서 많이 다뤄봤으므로 넘어가고, 큰 차이는 BFS는 큐를 이용해서 현재 노드를 확인하고, DFS는 재귀를 사용하는 방법으로 문제 해결이 가능하다.