[백준] 연결 요소의 개수 JAVA

반응형

728x90

[백준] 연결 요소의 개수

---

접근

• dfs
• bfs

---

풀이

정점과 간선의 정보가 주어지고 연결된 정점들을 한 덩어리로 쳤을 때 몇 개의 덩어리로 나눠지는지 구하는 문제이다. 문제에 방향 없는 그래프가 주어진 걸 보니 이 전에 풀었던 bfs와 dfs문제 코드를 약간만 수정하면 될 거 같아 들고 왔다.

2024.08.26 - [알고리즘/코딩테스트-백준] - [백준] DFS와 BFS JAVA

[백준] DFS와 BFS JAVA

 

이전에 DFS와 BFS에서 사용했던 코드와 거의 똑같다. DFS & BFS 문제에서는 탐색을 시작하는 정점의 번호가 주어졌고 이번 문제는 시작 정점의 정보가 필요가 없다.

	String[] NM = br.readLine().split(" ");
        int n = Integer.parseInt(NM[0]);
        int m = Integer.parseInt(NM[1]);

        List<Vertex> vertexes = new ArrayList<>();

        for (int i = 0; i <= n; i++) {
            vertexes.add(new Vertex(i));
        }

        for (int i = 0; i < m; i++) {
            String[] line = br.readLine().split(" ");
            int a = Integer.parseInt(line[0]);
            int b = Integer.parseInt(line[1]);

            vertexes.get(a).connectedVertexes.add(vertexes.get(b));
            vertexes.get(b).connectedVertexes.add(vertexes.get(a));
        }

문제의 입력에 맞게 입력 부분만 살짝 수정한 것 외에는 달라진 코드가 없다. 값들을 받아 각 정점을 양방향으로 연결해 주는 초기 작업은 동일하다.

private static class Vertex{
        private final int index;
        private final List<Vertex> connectedVertexes;

        public Vertex(int index) {
            this.index = index;
            connectedVertexes = new ArrayList<>();
        }
    }

전에 사용되었던 클래스도 수정된 것 없이 동일하다.

private static void bfs(Vertex start, boolean[] isVisited) {
        Queue<Vertex> queue = new LinkedList<>();
        queue.offer(start);
        isVisited[start.index] = true;

        while (!queue.isEmpty()) {
            Vertex vertex = queue.poll();
            List<Vertex> connectedVertexes = vertex.connectedVertexes;

            for (Vertex connectedVertex : connectedVertexes) {
                if(isVisited[connectedVertex.index])
                    continue;

                queue.offer(connectedVertex);
                isVisited[connectedVertex.index] = true;
            }
        }
    }

bfs의 코드로 이 전 문제에서는 탐색 순서 출력을 위해 출력문이 존재했던 부분과 정점 번호가 작은 순으로 탐색을 하기 위해 정렬을 해주었던 코드가 제거되는 것 외에는 달라진 부분이 없다.

private static void dfs(Vertex start, boolean[] isVisited) {
        Stack<Vertex> stk = new Stack<>();
        stk.push(start);

        while (!stk.isEmpty()) {
            Vertex vertex = stk.pop();
            List<Vertex> connectedVertexes = vertex.connectedVertexes;

            if(isVisited[vertex.index])
                continue;

            isVisited[vertex.index] = true;

            for (Vertex connectedVertex : connectedVertexes) {
                stk.push(connectedVertex);
            }
        }
    }

이 부분은 dfs코드로 동일하게 해당 부분만 제거되었다.

 

이 문제는 bfs나 dfs 둘 중에 아무거나 사용해서 풀면 되는 문제이고 단순한 연결 요소를 탐색하는 것에는 dfs와 bfs의 성능 차이는 거의 없다고 봐도 되는 편이다. 그렇지만 만들어져 있는 코드가 있기 때문에 하나씩 돌려보며 차이가 어느 정도 되는지 비교해 보기로 했다.

	boolean[] isVisitedBfs = new boolean[n + 1];
        boolean[] isVisitedDfs = new boolean[n + 1];

        /*int componentCountBfs = 0;
        for (int i = 1; i <= n; i++) {
            if (!isVisitedBfs[i]) {
                bfs(vertexes.get(i), isVisitedBfs);
                componentCountBfs++;
            }
        }*/

        int componentCountDfs = 0;
        for (int i = 1; i <= n; i++) {
            if (!isVisitedDfs[i]) {
                bfs(vertexes.get(i), isVisitedDfs);
                componentCountDfs++;
            }
        }

연결 요소의 개수를 구하는 파트이다. 정점을 1번부터 사용했기 때문에 i의 초기값은 1이 되고 방문하지 않은 정점이 있다면 bfs나 dfs를 수행하는 것이다. 첫 번째 정점에서 모든 정점이 다 연결되어 있다면 방문체크가 모두 완료되어 count의 수가 1인 상태로 반복문이 끝날 것이고 연결되지 않은 정점이 있다면 거기서 다시 탐색이 시작된다.

아래: BFS, 위: DFS

실제 BFS와 DFS 하나씩 돌려본 수행시간이다. 아래가 BFS, 위가 DFS로 거의 차이 없는 수행 시간을 보여준다.

---

전체 코드

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

public class Main {
    private static class Vertex{
        private final int index;
        private final List<Vertex> connectedVertexes;

        public Vertex(int index) {
            this.index = index;
            connectedVertexes = new ArrayList<>();
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] NM = br.readLine().split(" ");
        int n = Integer.parseInt(NM[0]);
        int m = Integer.parseInt(NM[1]);

        List<Vertex> vertexes = new ArrayList<>();

        for (int i = 0; i <= n; i++) {
            vertexes.add(new Vertex(i));
        }

        for (int i = 0; i < m; i++) {
            String[] line = br.readLine().split(" ");
            int a = Integer.parseInt(line[0]);
            int b = Integer.parseInt(line[1]);

            vertexes.get(a).connectedVertexes.add(vertexes.get(b));
            vertexes.get(b).connectedVertexes.add(vertexes.get(a));
        }

        boolean[] isVisitedBfs = new boolean[n + 1];
        boolean[] isVisitedDfs = new boolean[n + 1];

        /*int componentCountBfs = 0;
        for (int i = 1; i <= n; i++) {
            if (!isVisitedBfs[i]) {
                bfs(vertexes.get(i), isVisitedBfs);
                componentCountBfs++;
            }
        }*/

        int componentCountDfs = 0;
        for (int i = 1; i <= n; i++) {
            if (!isVisitedDfs[i]) {
                bfs(vertexes.get(i), isVisitedDfs);
                componentCountDfs++;
            }
        }

//        System.out.println(componentCountBfs);
        System.out.println(componentCountDfs);

        bw.flush();
        bw.close();
        br.close();
    }

    private static void bfs(Vertex start, boolean[] isVisited) {
        Queue<Vertex> queue = new LinkedList<>();
        queue.offer(start);
        isVisited[start.index] = true;

        while (!queue.isEmpty()) {
            Vertex vertex = queue.poll();
            List<Vertex> connectedVertexes = vertex.connectedVertexes;

            for (Vertex connectedVertex : connectedVertexes) {
                if(isVisited[connectedVertex.index])
                    continue;

                queue.offer(connectedVertex);
                isVisited[connectedVertex.index] = true;
            }
        }
    }
    private static void dfs(Vertex start, boolean[] isVisited) {
        Stack<Vertex> stk = new Stack<>();
        stk.push(start);

        while (!stk.isEmpty()) {
            Vertex vertex = stk.pop();
            List<Vertex> connectedVertexes = vertex.connectedVertexes;

            if(isVisited[vertex.index])
                continue;

            isVisited[vertex.index] = true;

            for (Vertex connectedVertex : connectedVertexes) {
                stk.push(connectedVertex);
            }
        }
    }
}