1260번 - BFS와 DFS

BFS와 DFS라는 실버 1 문제이다.

문제는 아래와 같다.

 

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

dfs() 메서드와 bfs() 메서드를 작성하여 문제를 풀 것이다.

 

DFS(깊이 우선 탐색)

 위와 같은 그래프가 있다. 

dfs는 말 그대로 깊은 곳부터 먼저 탐색하는 방법이다.

이렇게 1 -> 2 -> 5 -> 11로 그래프의 종단노드까지 쭉 진행한다.

종단 노드까지 진행되었다면, 바로 위에 노드에서 자식노드가 있나 검사한다.

1 -> 2 -> 5 -> 11 -> 12

또다시 종단 노드까지 진행되었다면 부모 노드에 자식이 있나 확인하고, 없으면 다시 부모노드를 확인해 종단노드까지 진행한다.

1 -> 2 -> 5 -> 11 -> 12 -> 6 -> 13

이렇게 쭉 진행하다보면 모든 노드를 확인할 수 있다.

 

마지막까지 진행했다가 다시 돌아오는 모습을 보면 재귀를 활용할 수 있겠다는 생각이 들어 아래처럼 코드를 작성했다.

static void dfs(int start) {
    visited[start] = true;
    dfsOutput.append(start + " ");
    if (sum == N) {
        return;
    }
    while (!dfsEdges.get(start).isEmpty()) {
        int next = dfsEdges.get(start).poll();
        if (!visited[next]) {
            sum++;
            dfs(next);
        }
    }
}

main메서드에서 visited[]는 N+1크기의 모두 false로 초기화 시켜 놓았다.

또한 간선 정보는 static List<PriorityQueue<Integer>> dfsEdges; 으로 지정해 놓았다.

사고 과정

1. start 정점에 들렸다고 기록한다.

2. 만약 모든 정점을 돌았다면, 메서드 호출이 종료된다.

3. 그렇지 않다면, 자식노드들을 살펴본다. 만일 들른적이 없는 자식 노드라면, 해당 자식노드에 들려준다(dfs(자식노드))

 

bfs(너비 우선 탐색)

위와 같은 그래프가 있다.

bfs 또한 말 그대로 맨 위에부터 하나씩 넓게 탐색하는 방법이다.

최상단에 위치한 노드의 자식 노드들을 먼저 탐색한다.

이후 그 다음 자식 노드들을 탐색한다.

또다시 그 자식 노드들을 탐색하며, 모든 노드가 탐색되었으면 끝이 난다.

 

이렇게 하나씩 탐색하는 것을 보면, queue에 자식 노드들을 담아두고 하나씩 빼주고 다시 그 자식을 queue에 넣어주면
순서가 꼬이지 않겠다라는 생각이 들었다.

static void bfs() {
    Queue<Integer> queue = new LinkedList<>();
    queue.add(V);
    while (!queue.isEmpty()) {
        if (sum == N) {
            return;
        }
        int start = queue.poll();
        while (!bfsEdges.get(start).isEmpty()) {
            int next = bfsEdges.get(start).poll();
            if (!visited[next]) {
                visited[next] = true;
                sum++;
                queue.add(next);
                bfsOutput.append(next + " ");
            }
        }
    }
}

1. 시작 노드를 큐에 넣어준다. 

2. 지금 노드의 모든 자식 노드를 큐에 넣어준다. 만일 자식 노드에 들린적이 있다면 큐에 포함시키지 않는다.

3. 큐가 비면 모든 경로를 탐색했다는 뜻이다. 코드는 종료된다.

 

전체코드

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

public class BFS와DFS_1260번 {
    static int N, M, V;
    static boolean[] visited;
    static List<PriorityQueue<Integer>> dfsEdges;
    static List<PriorityQueue<Integer>> bfsEdges;
    static StringBuilder dfsOutput;
    static StringBuilder bfsOutput;
    static int sum = 1;

    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());
        V = Integer.parseInt(st.nextToken());

        dfsEdges = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            dfsEdges.add(new PriorityQueue<>());
        }
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            dfsEdges.get(u).add(v);
            dfsEdges.get(v).add(u);
        }

        bfsEdges = new ArrayList<>();
        for (Queue<Integer> dfsQueue : dfsEdges) {
            PriorityQueue<Integer> bfsQueue = new PriorityQueue<>(dfsQueue);
            bfsEdges.add(bfsQueue);
        }

        visited = new boolean[N+1];
        dfsOutput = new StringBuilder();
        dfs(V);
        System.out.println(dfsOutput.toString());

        bfsOutput = new StringBuilder();
        bfsOutput.append(V + " ");
        sum = 1;
        visited = new boolean[N+1];
        visited[V] = true;
        bfs();
        System.out.println(bfsOutput.toString());

    }

    static void dfs(int start) {
        visited[start] = true;
        dfsOutput.append(start + " ");
        if (sum == N) {
            return;
        }
        while (!dfsEdges.get(start).isEmpty()) {
            int next = dfsEdges.get(start).poll();
            if (!visited[next]) {
                sum++;
                dfs(next);
            }
        }
    }

    static void bfs() {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(V);
        while (!queue.isEmpty()) {
            if (sum == N) {
                return;
            }
            int start = queue.poll();
            while (!bfsEdges.get(start).isEmpty()) {
                int next = bfsEdges.get(start).poll();
                if (!visited[next]) {
                    visited[next] = true;
                    sum++;
                    queue.add(next);
                    bfsOutput.append(next + " ");
                }
            }
        }
    }
}