[Java] DFS와 BFS

문제

[백준 1260번]
그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

 

입력

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

 

출력

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

 

 

예시

 

 

풀이

이 문제는 DFS(깊이 우선 탐색)과 BFS(너비 우선 탐색)의 가장 기본적인 백준 문제이다.

 

DFS는 순환이 있는지 검사할 때 주로 사용하고, BFS는 최단경로를 탐색할때 주로 사용한다.

 

0. 성공 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

//DFS와 BFS
public class Main {

    public static int[][] edges; //간선 기록을 위한 인접 행렬

    public static Set<Integer> visited = new HashSet<>(); //방문한 리스트

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st  = new StringTokenizer(br.readLine(), " ");

        //N = 정점의 개수
        int n = Integer.parseInt(st.nextToken());
        //M = 간선의 개수
        int m = Integer.parseInt(st.nextToken());
        //V = 탐색을 시작할 정점의 번호
        int v = Integer.parseInt(st.nextToken());

        edges = new int[n+1][n+1];

        for (int i = 0; i < m; i++) {
            st  = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            edges[a][b] = edges[b][a] = 1; // (a,b) 와 (b,a) 모두 기록
        }


        dfs(v);
        visited.clear();
        System.out.println();
        bfs(v);


    }

    public static void bfs(int source) {
        Queue<Integer> queue = new LinkedList<>();

        queue.offer(source); // Queue에 현재 노드 넣기

        visited.add(source); // 방문 기록

        while (!queue.isEmpty()) { // Queue가 빌 때까지 반복
            int current = queue.poll(); // Queue에서 현재 값 꺼내기
            System.out.printf(current + " ");

            //인접한 노드들 모두 방문
            for (int i = 0; i<edges[current].length; i++) {
                if (edges[current][i] == 1 && !visited.contains(i)) { // 인접 노드 중, 방문하지 않은 노드에 대해
                    queue.offer(i); // 해당 노드 Queue에 넣기
                    visited.add(i); //방문 기록
                }
            }
        }
    }

    public static void dfs(int source) {
        System.out.printf(source + " ");
        visited.add(source); // 노드 방문 기록

        for (int i = 0; i < edges[source].length; i++) {
            if (edges[source][i] == 1 && !visited.contains(i)) { // 만약 해당 노드를 방문한 적이 없다면
                dfs(i); // 해당 노드 방문
            }
        }
    }

}

 

1. 문제 풀이

input

public static int[][] edges; //간선 기록을 위한 인접 행렬

public static Set<Integer> visited = new HashSet<>(); //방문한 리스트

edges = new int[n+1][n+1];

        for (int i = 0; i < m; i++) {
            st  = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            edges[a][b] = edges[b][a] = 1; // (a,b) 와 (b,a) 모두 기록
        }

 

나는 간선 기록을 위해 인접 행렬 방식을 선택했다.

각 index에 따라 1을 표시함으로써 인접하다는 것을 나타낸다.

 

만약 예제로

4 5 1
1 2
1 3
1 4
2 4
3 4

 

가 들어왔다면, edges 는 아래와 같이 될 것이다.

 

 

 

각 index 0은 데이터가 의미가 없고, 1~4 사이 인접한 노드라면 1을 기록한다.

 

간선의 방향성이 없다면 사용 가능하며, 각 노드 모두 기록하기 때문에 edges[a][b]와 edges[b][a] 모두 1을 기록해주는게 중요하다.

 

방문한 기록은 중복이 상관없는 자료구조인 Set을 이용해 주었다.

 

 

DFS

public static void dfs(int source) {
    System.out.printf(source + " ");
    visited.add(source); // 노드 방문 기록

    for (int i = 0; i < edges[source].length; i++) {
        if (edges[source][i] == 1 && !visited.contains(i)) { // 만약 해당 노드를 방문한 적이 없다면
            dfs(i); // 해당 노드 방문
        }
    }
}

 

DFS는 재귀함수로 구현이 가능하다.

 

단순하게 인접한 노드가 방문하지 않았을 경우, 해당 노드에 대해 재귀 호출을 해주면 된다.

 

 

BFS

public static void bfs(int source) {
    Queue<Integer> queue = new LinkedList<>();

    queue.offer(source); // Queue에 현재 노드 넣기

    visited.add(source); // 방문 기록

    while (!queue.isEmpty()) { // Queue가 빌 때까지 반복
        int current = queue.poll(); // Queue에서 현재 값 꺼내기
        System.out.printf(current + " ");

        //인접한 노드들 모두 방문
        for (int i = 0; i<edges[current].length; i++) {
            if (edges[current][i] == 1 && !visited.contains(i)) { // 인접 노드 중, 방문하지 않은 노드에 대해
                queue.offer(i); // 해당 노드 Queue에 넣기
                visited.add(i); //방문 기록
            }
        }
    }
}

 

BFS는 Queue와같은 FIFO 자료구조를 통해 구현 가능하다.

 

인접한 노드들 중 방문하지 않은 노드들을 모두 Queue에 넣어놓고,

 

다시 while문이 돌아왔을 때 Queue가 비어있지 않다면 Queue에 있는 노드들을 다시 순차적으로 진행한다.

 

해당 while문이 반복된 횟수가 곧 깊이(depth)가 되겠다.