[ 탐색 ] BFS 너비 우선 탐색(백준 2178)

 BFS 너비 우선 탐색

너비 우선 탐색은 그래프 완전 탐색 기법 중 하나이다. -> DFS와 공통점
시작 노드에서 출발하여 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘

• FIFO 탐색
• 큐 자료구조 이용한다.
• 목표 노드에 도착하는 경로가 여러 개일 때 최단 경로를 보장한다.
• 시간 복잡도 : O(V+E) V: 노드 수, E: 에지 수
  
  

💡  BFS의 핵심 이론

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

visit배열을 사용하고 인접리스트를 사용하는 것은 DFS와 같다. 하지만 BFS는 스택이 아닌 큐를 사용한다.

 

 

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

큐에서 노드를 꺼내면서 해당 노드와 인접 노드를 큐에 삽입한다.

 

 

 

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

 

 

 2178 : 미로 탐색

문제

N×M크기의 배열로 표현되는 미로가 있다.

1	0	1	1	1	1
1	0	1	0	1	0
1	0	1	0	1	1
1	1	1	0	1	1

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

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

 

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

 

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

입력	출력
4 6 101111 101010 101011 111011	15
4 6 110110 110110 111111 111101	9

 

문제 풀이

• N, M의 최대 데이터 크기가 100으로 매우 작기 때문에 시간 제한은 별로로 고려하지 않아도 된다.
• 요구사항은 지나야 하는 칸 수의 최솟값을 찾는것이다.

 

실행 코드

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 P2178_BFS {
    // 상하좌우로 이동할 수 있는 좌표
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};

    static boolean[][] visited; // 방문여부 저장
    static int[][] A; // 미로 저장
    static int N; // y길이
    static int M; // x길이
    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());
        visited = new boolean[N][M];
        A = new int[N][M];
        
        // 데이터 삽입
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            String s = st.nextToken();
            // s에 저장된 문자열을 하나씩 끊어서 배열에 저장
            for(int j=0;j<M;j++){
                A[i][j] = Integer.parseInt(s.substring(j,j+1));
            }
        }

        // BFS
        BFS(0, 0);

        //출력
        System.out.println(A[N-1][M-1]);

    }

    private static void BFS(int x, int y) {
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{x, y}); // 좌표를 큐에 추가
        while(!q.isEmpty()){
            int[] cur = q.poll(); // 큐에 저장한 좌표를 뽑아서 방문처리하고
            visited[x][y] = true; // 현재 노드

            //상하좌우 탐색
            for(int k=0;k<4;k++){
                int nx = cur[0] + dx[k];
                int ny = cur[1] + dy[k];
                if(nx>=0 && ny>=0 && nx<N && ny<M){ // 배열을 넘어가면 안되고
                    if(!visited[nx][ny] && A[nx][ny]!=0){ // 0이 아니고 방문 안했을 때
                        // 이미 상하좌우 탐색으로 큐에 추가했던 좌표를 중복으로 넣는걸 방지한다.
                        visited[nx][ny] = true;
                        A[nx][ny] = A[cur[0]][cur[1]] + 1; //depth
                        q.add(new int[] {nx, ny}); //큐에 상하좌우 유효한 좌효표 추가
                    }
                }
            }
        }
    }
}

 

아무래도 그냥 혼자 풀라고 하면 못풀듯ㅋㅋ