그래프탐색 - DFS와 BFS

□ DFS와 BFS에 대한 개념 강의 영상

https://www.youtube.com/watch?v=_hxFgg7TLZQ&t=624s

 

 

□ 실행 코드

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    static int N, M, V; // 정점 수, 간선 수, 시작 점
    static int[][] graph; // 인접 행렬
    static boolean[] visited; // 방문 여부
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {

        String[] input = br.readLine().split(" ");

        N = Integer.parseInt(input[0]);
        M = Integer.parseInt(input[1]);
        V = Integer.parseInt(input[2]);

        graph(); // 그래프, 방문 배열 초기화 함수 호출
        DFS(V); // DFS 실행
        sb.append("\n");
        visited = new boolean[N + 1]; // BFS 실행을 위한 방문 여부 초기화
        BFS(V); // BFS 실행

        bw.write(sb.toString());
        bw.flush();

    }
}

 

1. 전역변수로 입력값(정점 수, 간선 수, 시작 점)과 그래프, 방문 여부 배열 선언
2. 입력값 초기화
3. 그래프 생성 함수 호출
4. DFS 실행
5. BFS 실행을 위한 방문 여부 배열 초기화
6. BFS 실행

□ 그래프 및 방문 여부 배열 만들기

- 코드보기

    // 그래프 그리기
    static void graph() throws IOException {
        graph = new int[N + 1][N + 1]; // 그래프 초기화
        visited = new boolean[N + 1]; // 방문 여부 초기화

        // 간선 정보 입력
        for (int i = 0; i < M; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            // 양방향 설정
            graph[a][b] = graph[b][a] = 1;
        }
    }

1. 정점의 수가 N개이므로 N + 1개로 초기화
   ex) N = 4이면 1, 2, 3, 4, 배열은 0부터 시작하기에 + 1
2. 간선 정보를 입력 받으며 양방향으로 설정

□ DFS(깊이 우선 탐색)(재귀 호출)

- 코드보기

    static void DFS(int node) {
        visited[node] = true; // 노드 방문 표시
        sb.append(node).append(" "); // 현재 노드 출력

        // 다음 간선 탐색
        for (int next = 1; next <= N; next++) {
            if (graph[node][next] == 1 && !visited[next]) { // 간선이 연결되어있고 방문하지않았으면 재귀 호출
                DFS(next);
            }
        }
    }

 

1. 시작 입력 값 V에 대해서 방문 처리 후 출력
2. 다음 연결된 간선을 탐색, 방문하지 않았다면 재귀 호출

□ BFS(너비 우선 탐색)(큐)

- 코드보기

 static void BFS(int start) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        visited[start] = true;

        // 큐가 비었을 때 까지 반복
        while (!queue.isEmpty()) {
            int node = queue.poll(); // 시작점 꺼내기
            sb.append(node).append(" ");

            // 다음 자식 노드 추가 작업
            for (int next = 1; next <= N; next++) {
                if (graph[node][next] == 1 && !visited[next]) { // 방문 여부 확인
                    queue.add(next); // 자식 노드 추가
                    visited[next] = true; // 방문처리
                }
            }
        }
    }

1. 큐 선언 및 초기화
2. 큐에 시작 값 V 추가 및 방문 처리
3. 큐가 비었을 때 까지 반복하면서 처리
4. 처음 node = start
5. start를 poll
6. 다음 연결된 값을 찾아서 추가 하고 방문 처리