[백준1260] DFS와 BFS 문제를 통해 그래프 탐색 이해하기

 

그래프 탐색의 목적: 임의의 정점에서 시작하여 연결되어 있는 모든 정점을 한 번씩 방문하는 것.

탐색 방법은 크게 2가지, DFS(깊이 우선 탐색)과 BFS(너비 우선 탐색)으로 나뉜다.

 

1. 깊이 우선 탐색(Depth First Search)

스택을 이용해 갈 수 있는 만큼 최대한 많이 간다.

더이상 갈 수 없으면 이전 정점으로 돌아간다.

 

재귀 호출을 이용해 구현 가능

void dfs(int x){
	check[x] = true;
    for(int i = 0; i < a[x].size(); i++){
        if(!checked[y]){
        	dfs(y);
        }
    }
}

 

2. 너비 우선 탐색(Breadth First Search)

큐를 이용해 지금 위치에 갈 수 있는 것을 모두 큐에 넣는 방식

큐에 넣을 때 방문했다고 체크한다

 

구현 방식

Queue<Integer> q = new LinkedList<>();

static void bfs(int x){
    check[x] = true;
    q.add(x);
    
    while (!q.isEmpty()) {
        int y = q.remove();
        for (int i = 1; i <= arr[x].size(); i++) {
            if (!check[i]) {
                check[i] = true;
                q.add(i);
            }
        }
    }
}

 

백준 문제로 실전연습

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

1260번: DFS와 BFS

 

1. 인접행렬을 통한 구현

 import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;

public class Main {
    static int n;
    static boolean[] check;
    static boolean[][] arr;

    static Queue<Integer> q = new LinkedList<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        int m = sc.nextInt();
        int v = sc.nextInt();

        arr = new boolean[n+1][n+1];
        check = new boolean[n+1];

        for (int i = 0; i < m; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();

            arr[a][b] = true;
            arr[b][a] = true;
        }

        dfs(v);
        System.out.println();
        check = new boolean[n+1];
        bfs(v);

    }

    static void dfs(int x){
        check[x] = true;
        System.out.print(x + " ");

        for (int i = 1; i <= n; i++) {
            if (arr[x][i] && !check[i]){
                dfs(i);
            }
        }
    }

    static void bfs(int x){
        check[x] = true;
        q.add(x);
        System.out.print(x + " ");

        while (!q.isEmpty()) {
            int y = q.remove();
            for (int i = 1; i <= n; i++) {
                if (arr[y][i] && !check[i]) {
                    check[i] = true;
                    q.add(i);
                    System.out.print(i +  " ");
                }
            }
        }
    }
}

 

2. 인접리스트를 통한 구현

>> "단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고" 라는 조건을 충족시키기 위해 정렬 시켜줘야함

import java.util.*;

public class Main {
    static List<Integer>[] arr;
    static boolean[] check;
    static String result = "";

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();
        int v = sc.nextInt();

        arr = new ArrayList[n + 1];
        check = new boolean[n + 1];

        for (int i = 1; i <= n; i++) {
            arr[i] = new ArrayList<>();
        }

        for (int i = 0; i < m; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();

            arr[a].add(b);
            arr[b].add(a);
        }

        for (int i = 1; i <= n; i++) {
            Collections.sort(arr[i]);
        }

        dfs(v);
        result += "\n";
        check = new boolean[n + 1];
        bfs(v);
        System.out.println(result);
    }

    static void dfs(int node){
        check[node] = true;
        result += node + " ";

        for (int i = 0; i < arr[node].size(); i++) {
            int y = arr[node].get(i);

            if (!check[y]) {
                dfs(y);
            }
        }
    }

    static void bfs(int node){
        Queue<Integer> q = new LinkedList<>();

        q.add(node);
        check[node] = true;

        while (!q.isEmpty()){
            int num = q.remove();
            result += num + " ";

            for (int i = 0; i < arr[num].size(); i++) {
                int num2 = arr[num].get(i);
                if(!check[num2]){
                    q.add(num2);
                    check[num2] = true;
                }
            }
        }
    }
}