# 너비 우선 탐색

### BFS

* 너비 우선 탐색(BFS)도 그래프를 완전 탐색하는 방법 중 하나로, 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘이다.
* BFS는 FIFO 방식으로 탐색하고 Queue를 이용해 구현한다. 노드 수가 V, 에지 수가 E라고 했을 때 시간 복잡도는 O(V + E)가 된다.
* 너비 우선 탐색은 탐색 시작 노드와 가까운 노드를 우선하여 탐색하므로 목표 노드에 도착하는 경로가 여러 개일 때 최단 경로를 보장한다.



### **핵심 이론**

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

    • 노드는 다시 방문하지 않으므로 방문한 노드를 체크하기 위한 배열이 필요하다. 그리프를 인접 리스트로 표현하는 것 역시 DFS와 동일하다. 탐색을 위해 스택이 아닌 큐를 사용한다.
2. 큐에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 큐에 삽입하기
3. 큐 자료구조에 값이 없을 때까지 반복하기



### DFS와 BFS 프로그램 (1260)

#### Question

![](https://2669959621-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FxncaDDrGpdjhVy86HbwM%2Fuploads%2FLLgytkFK1cd6p410orEN%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202022-06-10%20%E1%84%8B%E1%85%A9%E1%84%8C%E1%85%A5%E1%86%AB%207.18.44.png?alt=media\&token=4572778b-d258-4f51-82e3-97db74e3886c)

#### Code&#x20;

{% tabs %}
{% tab title="First Tab" %}
```java
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);
                }
            }
        }
    }
}

```


{% endtab %}

{% tab title="Untitled" %}
```java

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 int node;
    static int edge;
    static int start;

    static ArrayList<Integer>[] A;

    static boolean visited[];
    static Queue<Integer> Q;

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

        node = sc.nextInt();
        edge = sc.nextInt();
        start = sc.nextInt();

        visited = new boolean[node+1];
        A = new ArrayList[node+1];
        Q = new LinkedList<>();

        // 각 노드 배열 초기화하기
        for (int i = 1; i <= node; i++) {
            A[i] = new ArrayList<Integer>();
        }

        // 노드 연결된 값 추가
        for (int i = 0; i < edge; i++) {
            int S = sc.nextInt();
            int E = sc.nextInt();
            A[S].add(E);
            A[E].add(S);
        }

        // 인접 리스트 정렬하기
        for (int i = 1; i <= node; i++) {
            Collections.sort(A[i]);
        }

        // DFS
        visited = new boolean[node + 1];
        DFS(start);

        System.out.print("\n");

        // BFS
        visited = new boolean[node + 1];
        Q.add(start);
        visited[start] = true;
        BFS(start);


    }


    public static void DFS(int i) {

        if (visited[i]) {
            return;
        }
        else {
            visited[i] = true;
            System.out.print(i + " ");
        }

        for (int k : A[i]) {
            DFS(k);
        }
    }

    public static void BFS(int i) {


        for (int k : A[i]) {
            if (!visited[k]) {
                Q.add(k);
                visited[k] = true;
            }
        }
        if (!Q.isEmpty()) {
            int now = Q.poll();
            System.out.print(now + " ");
            BFS(now);
        }
    }

}

```
{% endtab %}
{% endtabs %}

#### Insight

#### Idea

#### reference



### 미로 탐색하기

#### Question -2178

![](https://2669959621-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FxncaDDrGpdjhVy86HbwM%2Fuploads%2Fo3csPrAKVWPIoaDAO5wi%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202022-08-01%20%E1%84%8B%E1%85%A9%E1%84%92%E1%85%AE%205.26.38.png?alt=media\&token=5e94838f-6880-4e23-8451-26dc2788aa97)

#### Code

```java
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

* 그래프 이론
* 그래프 탐색
* 너비 우선 탐색&#x20;

#### reference



### 트리의 지름 구하기

#### Question - 1167

![](https://2669959621-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FxncaDDrGpdjhVy86HbwM%2Fuploads%2FjryKCJ5j5sEa9ooX94tF%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202022-08-01%20%E1%84%8B%E1%85%A9%E1%84%92%E1%85%AE%205.27.03.png?alt=media\&token=b6a55b5d-96c1-4183-9e29-0de2fafa0f63)

#### Code

```java

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

