Stunning-PS

BFS - Nathan

 
  • Nathan Hong
  • Apr 20, 2021

너비 우선 탐색

image

  • 시작 정점으로부터 인접한 정점들을 모두 차례로 방문하고 나서,방문했던 정점을 시작으로 하여 다시 인접한 정점들을 차례로 방문하는 방식
  • 가까운 정점들을 먼저 방문하고 멀리있는 정점들은 나중에 방문하는 순회방법
  • 인접한 정점들에 대해서 차례로 다시 너비 우선 탐색을 반복해야하므로 선입선출의 구조를 갖는 큐를 사용

너비 우선 탐색의 수행순서

(1) 시작 정점 𝑣를 결정하여 방문한다.

(2) 정점 𝑣에 인접한 정점들 중에서 방문하지 않은 정점을 차례로 방문하면서 큐에 enQueue한다.

(3) 방문하지 않은 인접한 정점이 없으면, 방문했던 정점에서 인접한 정점들을 다시 차례로 방문하기 위해서 큐에서 deQueue하여 구한 정점 에서 (2)를 반복한다.

(4) 큐가 공백이 될 때까지 (2)~(3)을 반복한다

너비 우선순위 코드

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

        while (!queue.isEmpty()) {
            int a = queue.poll();
            System.out.println(a);
            for (Integer s : graph.get(a)) {
                if (!visited[s]) {
                    visited[s] = true;
                    queue.add(s);
                }
            }
        }
    }

출력결과

1
3
2
7
6
5
4
9
8

너비 우선 탐색 활용

  • 너비 우선 탐색의 경우 그래프 탐색의 많이 활용되고 “경로”문제나 시뮬레이션 문제에 자주 나온다.
  • 너비 우선 탐색의 경우 최단 거리 구하는 문제로 자주 활용되는데, 아래 백준의 문제 예시로 한번 풀어보자.

문제

2178번: 미로 탐색

  • N×M크기의 배열로 표현되는 미로가 있다.
  • 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다.
    • 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

  • 위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

  • 위 문제를 한 줄로 요약하면 (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하는 것이다.

문제 풀이

  • 서로 인접한 칸으로만 이동 가능하기 때문에 위 아래 오른쪽 왼쪽 탐색 진행.
  • 위 아래 오른쪽 왼쪽을 모두 탐색하면서 방문하지 않은 칸에는 현재 칸의 숫자 + 1을 하면서 탐색을 진행
  • 최종적으로 N, M까지 너비 우선 탐색을 하면서 진행하면 N,M에는 최소 칸의 수가 적혀 있음.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

class Node {
    int x;
    int y;

    public Node(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

public class baekjoon2178 {

    public static int n;

    public static int m;

    public static int[][] map;

    public static boolean[][] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] st = br.readLine().split(" ");
        n = Integer.parseInt(st[0]);
        m = Integer.parseInt(st[1]);
        map = new int[n+1][m+1];
        visited = new boolean[n+1][m+1];

        for (int i = 1; i <= n; i++) {
            String s = br.readLine();
            for (int j = 0; j < s.length(); j++) {
                map[i][j+1] = Integer.parseInt(String.valueOf(s.charAt(j)));
            }
        }

        bfs();
        System.out.println(map[n][m]);
    }

    public static void bfs() {
        int[] dx = {0, 0, 1, -1};
        int[] dy = {1, -1, 0, 0};
        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(1, 1));

        while (!queue.isEmpty()) {
            Node node = queue.poll();
            int x = node.x;
            int y = node.y;

            for (int i = 0; i < 4; i++) {
                int mx = x + dx[i];
                int my = y + dy[i];
                if (mx > 0 && my > 0 && mx <= n && my <= m) {
                    if (!visited[mx][my] && map[mx][my] == 1) {
                        visited[mx][my] = true;
                        map[mx][my] = map[x][y] + 1;
                        queue.add(new Node(mx, my));
                    }
                }
            }
        }
    }
}
Search