[백준] 1260번 DFS와 BFS 자바

DFS 문제 따로 BFS 문제 따로 풀어본 적은 있는데 한 문제에서 동일한 그래프로 DFS와 BFS를 모두 사용해야 하는 문제였습니다.

 

🔗 문제 링크

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

1260번: DFS와 BFS

 

 

 

🔍 문제 분석

• 첫 째줄에 정점의 개수(N, 노드의 개수)와 간선의 개수(M) 그리고 탐색 시작 정점(V)이 공백으로 주어집니다.
• 그다음 간선의 개수(M)만큼의 입력이 주어지고, 각 입력 줄에는 연결되어 있는 Node와 Node가 공백으로 주어집니다.
• 정점의 번호는 1번부터 N번까지 이며, DFS 탐색 결과와 BFS 탐색 결과를 출력해 주면 되는 문제입니다.
• 여기서 신경써줘야 할 점은 연결된 Node가 여러 개라면 크기가 작은 것부터 탐색을 시작합니다.

 

 

 

🖥️ 문제 풀이 코드

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

public class Main {
    static int n;
    static StringBuilder builder;
    static boolean[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        String[] inputData = reader.readLine().split(" ");
        n = Integer.parseInt(inputData[0]);
        int m = Integer.parseInt(inputData[1]);
        int v = Integer.parseInt(inputData[2]);

        // step 1. 그래프 만들기
        int[][] graph = new int[n + 1][n + 1];
        for (int i = 0; i < m; i++) {
            inputData = reader.readLine().split(" ");
            int startNum = Integer.parseInt(inputData[0]);
            int endNum = Integer.parseInt(inputData[1]);

            graph[startNum][endNum] = 1;
            graph[endNum][startNum] = 1;
        }
        builder = new StringBuilder();
        visited = new boolean[n + 1];
        dfs(v, graph);
        builder.append("\n");
        visited = new boolean[n + 1];
        bfs(v, graph);
        System.out.println(builder);
    }

    // step 2. BFS 탐색 (Queue)
    public static void bfs(int start, int[][] graph) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        visited[start] = true;

        while (!queue.isEmpty()) {
            int vortex = queue.poll();
            builder.append(vortex).append(" ");
            int[] vortexWithNodes = graph[vortex];

            for (int i = 1; i <= n; i++) {
                if (vortexWithNodes[i] == 1 && !visited[i]) {
                    queue.offer(i);
                    visited[i] = true;
                }
            }
        }
    }

    // step 3. DFS 탐색 (재귀)
    public static void dfs(int start, int[][] graph) {
        visited[start] = true;
        builder.append(start).append(" ");
        int[] startWithNodes = graph[start];

        for (int i = 1; i <= n; i++) {
            if (startWithNodes[i] == 1 && !visited[i]) {
                dfs(i, graph);
            }
        }
    }
}

 

• 처음에 Graph를 어떤 방식으로 해놓을지 고민했었습니다. 첫 번째 방법은 위에 구현한 방법과 같은 인접 행렬 방법을 사용하는 방법이 있고, 두 번째는 각 노드에 연결된 점들을 리스트에 모아두는 인접 리스트 방법이 존재합니다.
• 인접 행렬 방법을 선택한 이유는 간단합니다. "연결된 노드가 여러 개라면 크기가 작은 노드부터 방문합니다."라는 조건에서 연결된 Node들이 정렬되어 있어야 된다는 것 때문입니다.
• 만약 인접 리스트 방법을 사용했다면, 연결된 노드들을 정렬해 주는 Collections.sort()를 사용해야 됐습니다.

 

 

 

🧑🏻‍💻 문제 풀이 전략

1. BFS는 Queue를 이용해서 구현했습니다.

public static void bfs(int start, int[][] graph) {
    Queue<Integer> queue = new LinkedList<>();
    queue.offer(start);
    visited[start] = true;

    while (!queue.isEmpty()) {
        int vortex = queue.poll();
        builder.append(vortex).append(" ");
        int[] vortexWithNodes = graph[vortex];

        for (int i = 1; i <= n; i++) {
            if (vortexWithNodes[i] == 1 && !visited[i]) { // <-- 이미 탐색한 노드인지 확인
                queue.offer(i);
                visited[i] = true;
            }
        }
    }
}

• 큐(Queue)를 통해서 탐색 노드에 연결된 노드들을 모두 탐색하고, 탐색이 가능한 데이터(값이 1이고, 방문기록이 false인 노드)라면 Queue에 모두 넣습니다.
• 이때 Queue에 넣으면서 해당 노드의 방문처리를 해줘야 합니다.
• Queue에 데이터가 없을 때까지 반복하여 BFS 탐색을 진행합니다.

 

2. DFS는 재귀를 이용해서 구현했습니다.

public static void dfs(int start, int[][] graph) {
    visited[start] = true;
    builder.append(start).append(" ");
    int[] startWithNodes = graph[start];

    for (int i = 1; i <= n; i++) {
        if (startWithNodes[i] == 1 && !visited[i]) { // <-- 이미 탐색한 노드인지 확인
            dfs(i, graph);
        }
    }
}

• 재귀를 통해서 가장 깊은 곳까지 탐색을 하고, 더이상 탐색할 데이터가 없으면 빠져나오게 됩니다.

 

3. Graph와 Visited는 공유하는 데이터입니다.

• 그래프 탐색을 하는데 있어서 Graph의 내부 값을 변경시키지는 않습니다.
• 하지만 Visited는 값을 false에서 true로 변경시키며 탐색하기 때문에 static으로 선언해서 탐색 시작 전에 new boolean[]으로 초기화를 진행해줬습니다.

visited = new boolean[n + 1]; // <-- 탐색 전 초기화
dfs(v, graph);

visited = new boolean[n + 1]; // <-- 탐색 전 초기화
bfs(v, graph);