[백준] DFS와 BFS JAVA

728x90

DFS와 BFS

---

접근

• dfs
• bfs

---

풀이

이름에 나와 있는 것처럼 DFS와 BFS를 구현해 보는 문제이다. 정점과 간선의 정보가 주어지고 DFS와 BFS로 탐색되는 순서를 출력하는 문제이다. 우선 정점의 정보를 담을 클래스를 선언한다.

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

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

정점은 자신의 번호와 연결된 정점들의 정보를 가진다.

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

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

정점의 개수만큼 정점을 생성해 준다. 0번 정점은 사용하지 않는다.

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];

dfs(vertexes.get(v), isVisitedDfs, bw);
bw.write("\n");
bfs(vertexes.get(v), isVisitedBfs, bw);

방문체크 배열과 실행문이다. 이제 문제인 DFS와 BFS 구현이 남았다. DFS란 Depth First Search로 깊이 우선 탐색 방법이다. 그래프나 트리에서 정점을 탐색하는 방법으로 가능한 깊이 들어가 탐색을 진행하고 더 이상 탐색이 불가능하다면 다시 이전 정점으로 돌아와 탐색을 이어가는 구조다.

    A
   / \
  B   C
 / \
D   E
   /
  F

그래프의 형태가 위와 같을 경우 A에서 탐색을 시작한다고 가정하자. B와 C 중 진행할 방향을 고를 수 있는데 B를 골랐다 치면 B에서 깊숙하게 모든 경로를 다 탐색한 후에 C를 탐색한다. A - B - D -> A - B - E - F -> A - C 순서로 더 이상 진행할 수 없는 곳까지 진행을 한 후에 돌아가 다른 경로를 탐색한다. dfs는 스택으로 bfs는 큐를 이용해 구현하였다.

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

    while (!stk.isEmpty()) {
        Vertex vertex = stk.pop();
        List<Vertex> connectedVertexes = vertex.connectedVertexes;
        connectedVertexes.sort((a,b) -> b.index - a.index);

        if(isVisited[vertex.index])
            continue;

        isVisited[vertex.index] = true;

        bw.write(String.valueOf(vertex.index) + " ");

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

스택에 탐색의 시작점이 되는 정점을 넣고 탐색을 시작한다. 문제의 조건에 해당 정점에 연결된 간선이 여러 개일 경우 정점 번호가 작은 순으로 먼저 탐색을 진행한다는 조건이 있어 dfs는 연결된 정점들을 내림차순으로 정렬해 주었고 bfs는 오름차순으로 정렬해 주었다. dfs에는 스택이 사용되기 때문에 탐색이 먼저 진행되기 위해선 스택에 가장 마지막에 추가되어야 하므로 내림차순으로 정렬하여야 작은 순으로 탐색이 가능하다.

 

로직으로는 dfs는 스택에서 꺼낸 현재 정점의 방문 체크를 먼저 하고 만약 방문하지 않았다면 방문을 하고 주변 정점을 스택에 추가한다. 방문체크를 먼저 하는 이유는 위에 그래프에서 A-B-D를 탐색한 후 다시 B로 돌아가기 때문에 방문체크를 먼저 해주지 않는다면 이미 추가되어 있는 정점들이 다시 추가되기 때문에 방문체크를 한 뒤 넣어준다. BFS란 Breadth-First Search로 너비 우선 탐색 알고리즘이다. 탐색을 시작한 정점에서 인근 정점을 우선으로 탐색한 후에 다음 레벨 정점을 탐색한다.

    A
   / \
  B   C
 / \
D   E
   /
  F

아까와 동일한 그래프로 A에서 탐색을 시작한다고 가정할 때 인접 정점인 B와 C를 탐색을 하고 그다음 레벨인 D와 E를 탐색하고 그다음 F를 탐색한다. A-B-C -> D-E -> F 순서로 같은 레벨의 정점을 모두 탐색한 후에 다음 레벨로 넘어간다.

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

    while (!queue.isEmpty()) {
        Vertex vertex = queue.poll();
        List<Vertex> connectedVertexes = vertex.connectedVertexes;
        connectedVertexes.sort(Comparator.comparingInt(a -> a.index));

        bw.write(String.valueOf(vertex.index) + " ");

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

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

bfs의 코드이다. bfs는 큐를 이용해 구현되기 때문에 오름차순으로 정렬해 주어 정점 번호가 낮은 순으로 탐색을 진행해 주었다. 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[] NMV = br.readLine().split(" ");
        int n = Integer.parseInt(NMV[0]);
        int m = Integer.parseInt(NMV[1]);
        int v = Integer.parseInt(NMV[2]);

        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];


        dfs(vertexes.get(v), isVisitedDfs, bw);
        bw.write("\n");
        bfs(vertexes.get(v), isVisitedBfs, bw);

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

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

        while (!queue.isEmpty()) {
            Vertex vertex = queue.poll();
            List<Vertex> connectedVertexes = vertex.connectedVertexes;
            connectedVertexes.sort(Comparator.comparingInt(a -> a.index));

            bw.write(String.valueOf(vertex.index) + " ");

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

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

        while (!stk.isEmpty()) {
            Vertex vertex = stk.pop();
            List<Vertex> connectedVertexes = vertex.connectedVertexes;
            connectedVertexes.sort((a,b) -> b.index - a.index);

            if(isVisited[vertex.index])
                continue;

            isVisited[vertex.index] = true;

            bw.write(String.valueOf(vertex.index) + " ");

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

순수 알고리즘 구현 문제로 복잡할 것 없는 문제이지만 알고리즘의 정의를 그대로 구현하는 문제이기 때문에 도움이 되는 문제이다.