너비 우선 탐색

BFS

  • 너비 우선 탐색(BFS)도 그래프를 완전 탐색하는 방법 중 하나로, 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘이다.

  • BFS는 FIFO 방식으로 탐색하고 Queue를 이용해 구현한다. 노드 수가 V, 에지 수가 E라고 했을 때 시간 복잡도는 O(V + E)가 된다.

  • 너비 우선 탐색은 탐색 시작 노드와 가까운 노드를 우선하여 탐색하므로 목표 노드에 도착하는 경로가 여러 개일 때 최단 경로를 보장한다.

핵심 이론

  1. BFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기

    • 노드는 다시 방문하지 않으므로 방문한 노드를 체크하기 위한 배열이 필요하다. 그리프를 인접 리스트로 표현하는 것 역시 DFS와 동일하다. 탐색을 위해 스택이 아닌 큐를 사용한다.

  2. 큐에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 큐에 삽입하기

  3. 큐 자료구조에 값이 없을 때까지 반복하기

DFS와 BFS 프로그램 (1260)

Question

Code 

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

public class N26_1206_DFS_BFS {

    static boolean visited[];
    static ArrayList<Integer>[] A;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int node = sc.nextInt();
        int edge = sc.nextInt();
        int start = sc.nextInt();

        A = new ArrayList[node + 1];

        for (int i = 1; i <= node; i++) {
            A[i] = new ArrayList<Integer>();
        }

        for (int i = 0; i < edge; i++) {
            int E = sc.nextInt();
            int S = sc.nextInt();

            A[E].add(S);
            A[S].add(E);
        }

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

        visited = new boolean[node +1];
        DFS(start);
        System.out.println();

        visited = new boolean[node + 1];
        BFS(start);
        System.out.println();
    }

    public static void DFS(int Node) {
        System.out.print(Node + " ");
        visited[Node] = true;
        for (int i : A[Node]) {
            if (!visited[i]) {
                DFS(i);
            }
        }
    }

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

        while (!q.isEmpty()) {
            int pop = q.poll();
            System.out.print(pop + " ");
            for (int i : A[pop]) {
                if(!visited[i]) {
                    visited[i] = true;
                    q.add(i);
                }
            }
        }
    }
}

Insight

Idea

reference

미로 탐색하기

Question -2178

Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class N27_P2178_미로_탐색하기 {

    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};
    static boolean[][] visited;
    static int[][] A;
    static int N, M;

    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());

        A = new int[N][M];
        visited = new boolean[N][M];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            String line = st.nextToken();
            for (int j = 0; j < M; j++) {
                A[i][j] = Integer.parseInt(line.substring(j, j + 1));
            }
        }
        BFS(0, 0);
        System.out.println(A[N - 1][M - 1]);

    }

    public static void BFS(int i, int j) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{i, j});
        while (!queue.isEmpty()) {
            int now[] = queue.poll();
            visited[i][j] = true;
            for (int k = 0; k < 4; k++) {
                int x = now[0] + dx[k];
                int y = now[1] + dy[k];
                if (x >= 0 && y >= 0 && x < N && y < M) {
                    if (A[x][y] != 0 && !visited[x][y]) {
                        visited[x][y] = true;
                        A[x][y] = A[now[0]][now[1]] + 1;
                        queue.add(new int[]{x, y});
                    }
                }
            }
        }
    }
}

Insight

Idea

  • 그래프 이론

  • 그래프 탐색

  • 너비 우선 탐색

reference

트리의 지름 구하기

Question - 1167

Code


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

public class N28_P1167_트리의_지름_구하기 {

    static boolean visited[];
    static int[] distance;

    static ArrayList<Edge>[] A;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        A = new ArrayList[N + 1]; // 1부터 시작

        for (int i = 1; i <= N; i++) { // 1부터 시
            A[i] = new ArrayList<Edge>();
        }

        for (int i = 0; i < N; i++) {
            int S = sc.nextInt();
            while (true) {
                int E = sc.nextInt();
                if (E == -1)
                    break;
                int V = sc.nextInt();
                A[S].add(new Edge(E, V));
            }
        }

        distance = new int[N + 1];
        visited = new boolean[N + 1];
        BFS(1);

        int Max = 1;
        for (int i = 2; i <= N; i++) {
            if (distance[Max] < distance[i])
                Max = i;
        }

        distance = new int[N + 1];
        visited = new boolean[N + 1];
        BFS(Max);
        Arrays.sort(distance);
        System.out.println(distance[N]);
    }

    private static void BFS(int index) {
        Queue<Integer> q = new LinkedList<>();
        q.add(index);
        visited[index] = true;
        while (!q.isEmpty()) {
            int now = q.poll();
            for (Edge i : A[now]) {
                int e = i.e;
                int v = i.value;
                if (!visited[e]) {
                    visited[e] = true;
                    q.add(e);
                    distance[e] = distance[now] + v;
                }
            }
        }
    }
}
class Edge { // 에지 클래스
    int e;
    int value;

    public Edge(int e, int value) {
        this.e = e;
        this.value = value;
    }
}

Insight

Idea

  • 트리

  • 그래프 탐색

  • 트리

  • 깊이 우선 탐색

reference

Previous깊이 우선 탐색Next이진 탐색

Last updated