너비 우선 탐색(Breath First Search)

너비 우선 탐색(Breath First Search, BFS) - 시작점에서 가까운 정점부터 순서대로 방문을 하는 탐색 알고리즘이다. 큐와 같이 사용된다.

 - 최단 경로를 구할 때 목적지를 찾자마자 최단경로임이 보장되어 탐색을 종료할 수 있는 장점이 있다. 

 - 가까운 정점을 모두 저장해놓고 순서대로 방문해야 하므로 스택 구조는 구현이 어렵고 큐를 사용.

 

                                                       그림을 보며 이해를 해보자.

1에서 시작을 한다. 1은 큐에 저장 된다.

1에서 인접한 노드를 방문한다. 방문한 1은 큐에서 꺼내고 방문한적 없는 노드인 2, 3을 큐에 넣어준다.

방문한 2, 3 은 큐에서 꺼내고 방문한적없는 4, 5를 큐에 넣어준다.

모든 노드가 방문처리 되면 남은 노드들을 큐에서 꺼내준다. 

큐에서 꺼낸 순서는 1, 2, 3, 4, 5이다.

이와 같이 1부터 가가운 노드들부터 탐색이 이루어지는 것이 너비우선탐색이다.

 

백준알고리즘(문제 2178)을 적용하여 보자.

 

 

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 Main {
 
    static int[] dir_x = {1,-1,0,0};
    static int[] dir_y = {0,0,-1,1};
    static boolean[][] visited;
    static int[][] map;
    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()); // StringTokenizer는 긴 문자열을 지정된 구분자를 기준으로 문자열을 슬라이싱
 
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
 
        map = 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++) {
                map[i][j] = line.charAt(j) - '0';
            }
        }
 
        bfs(0,0);
 
        System.out.println(map[N-1][M-1]);
    }
 
    // Queue 메서트
    // offer -> Queue에 객체를 저장, poll-> Queue에서 객체를 꺼내서 반환.
    public static void bfs(int i, int j){
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[] {i,j});
 
        while(!q.isEmpty()){
            int location[] = q.poll();
            visited[i][j] = true;
 
            for(int dir = 0; dir<4; dir++){
                int r = location[0] + dir_x[dir];
                int c = location[1] + dir_y[dir];
 
                //좌표가 -1이 되거나 N or M이 되어 map의 범위를 제어
                if(r >= 0 && c >= 0 && r < N && c < M){
                    if(map[r][c] != 0 && !visited[r][c]){
                        q.offer(new int[] {r,c});
                        visited[r][c] = true;
                        map[r][c] = map[location[0]][location[1]] + 1;
                    }
                }
            }
        }
    }
}