BOJ01260 DFS와 BFS

https://www.acmicpc.net/problem/1260 (opens new window)

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력한다.

DFS 활용

깊이를 우선적으로 탐색한다. 재귀 혹은 Stack 자료구조를 활용한다.

private static void dfs(int v) {
    // 현재 노드 방문 처리
    visited[v] = true;
    System.out.print(v + " ");
    // 현재 노드와 연결된 다른 노드 재귀적 방문
    for (int i = 0; i < array[v].length; i++) {
        if (array[v][i] == 1 && !visited[i]) {
            dfs(i);
        }
    }
}

BFS 활용

너비를 우선적으로 탐색한다. Queue 자료구조를 활용한다.

private static void bfs(int v) {
    Queue<Integer> queue = new LinkedList<>();
    queue.offer(v);
    // 현재 노드 방문 처리
    visited[v] = true;
    // 큐가 빌 때까지 반복
    while (!queue.isEmpty()) {
        // 큐에서 하나의 원소를 뽑아 출력
        v = queue.poll();
        System.out.print(v + " ");
        // 해당 원소와 연결된, 방문하지 않은 원소 큐에 삽입
        for (int i = 0; i < array[v].length; i++) {
            if (array[v][i] == 1 && !visited[i]) {
                queue.offer(i);
                visited[i] = true;
            }
        }
    }
}

제출 코드

위에서 작성한 DFS, BFS를 활용하여 적용한다. 아래는 최종 제출 코드이다.

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

public class BOJ1260 {

    public static int[][] array;
    public static boolean[] visited;

    private static void dfs(int v) {
        // 현재 노드 방문 처리
        visited[v] = true;
        System.out.print(v + " ");
        // 현재 노드와 연결된 다른 노드 재귀적 방문
        for (int i = 0; i < array[v].length; i++) {
            if (array[v][i] == 1 && !visited[i]) {
                dfs(i);
            }
        }
    }

    private static void bfs(int v) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(v);
        // 현재 노드 방문 처리
        visited[v] = true;
        // 큐가 빌 때까지 반복
        while (!queue.isEmpty()) {
            // 큐에서 하나의 원소를 뽑아 출력
            v = queue.poll();
            System.out.print(v + " ");
            // 해당 원소와 연결된, 방문하지 않은 원소 큐에 삽입
            for (int i = 0; i < array[v].length; i++) {
                if (array[v][i] == 1 && !visited[i]) {
                    queue.offer(i);
                    visited[i] = true;
                }
            }
        }
    }

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

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

        // 그래프 초기화
        array = new int[n + 1][n + 1];
        visited = new boolean[n + 1];

        for (int i = 0; i < m; i++) {
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            array[x][y] = 1;
            array[y][x] = 1;
        }

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

#algorithm #BOJ #그래프 이론 #그래프 탐색 #너비 우선 탐색 #깊이 우선 탐색 #BFS #DFS