BFS - 백준2178 미로 탐색

첫 BFS 문제이다
BFS는 기본적인 코드 틀이 있다고 한다.

준비물
0. 좌표 클래스
ex) new Pair(x, y)
1. boundary exception 체크용 배열
ex) int[] bx = {1, 0, -1, 0};
int[] by = {0, 1, 0, -1};
2. 위치(Pair)를 보관하는 큐

코드
1. 일단 큐에 첫번째 위치 add()
2. while(큐가 빌 때 까지)
3. 큐의 element 하나 꺼내기
4. for(동, 서, 남, 북 4번)
4 -1. 현재 위치를 element의 동/서/남/북 중 한 곳 지정
ex) int px = element.x + bx[i];
int py = element.y + bx[i];
5. if (px, py가 배열의 범위 안에 있는지 확인)
ex) if (px < 0 || px >= endX || py < 0 || py >= endY) continue;
6. if(px,py의 위치가 방문한 곳이거나 벽이 아닌지 확인)
7. 5, 6이 아니면 배열의 px, py위치에 방문표시 후, 큐에 현재 위치 추가

boundary exception을 체크하기 위해 2개의 배열과 반복문을 사용하는 점 빼면 논리적으로 당연한 코드라서 외우기 어렵지 않다.

본 문제는 이를 응용해서 미로의 목적지까지 최단 거리를 구하는 문제이다.

풀이
나는 Pair클래스에 정수형 변수를 하나 더 만들어, 해당 좌표까지의 거리를 저장했다.
그리고 그 좌표를 꺼내서 그 다음 칸을 탐색하여 큐에 저장할 때 거리를 +1 해서 저장했다.
모든 루프가 끝나면 목적지칸에 저장된 거리변수를 출력한다.

import java.util.*;
import java.io.*;

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        
        int[][] array = new int[n][m];
        
        for(int i = 0; i < n; i++){
            String readArrayLine = br.readLine();
            for(int j = 0; j < m; j++){
                int tmp = readArrayLine.charAt(j) - '0';
                if(tmp == 0){
                    array[i][j] = -1;
                }else if(tmp == 1){
                    array[i][j] = 0;
                }
                
            }
        }
        
        //bfs
        //동서남북배열
        //원본배열
        int[] bx = {1, 0, -1, 0};
        int[] by = {0, 1, 0, -1};
        
        Queue<Pair> queue = new LinkedList<>();
        
        //첫번째 집어넣기
        queue.add(new Pair(0,0,1));
        array[0][0] = 1;
        
        //while(큐가 빌때까지)
        //첫번째 element pop
        //for(동,서,남,북)
        //if(boundary exception테스트)
        //if(벽or방문한곳 아닌지)
        //방문후, 큐에 push
        

        // 벽은 -1, 길은 0, 방문한곳은 1~n
        while(!queue.isEmpty()){
            
            //현재위치
            Pair nowPos = queue.poll();
            //현재위치의 거리
            int dis = nowPos.distance + 1;
            
            for(int i = 0; i < 4; i++){
                int px = nowPos.x + bx[i];
                int py = nowPos.y + by[i];
                
                if(px < 0 || px > n-1 || py < 0 || py > m-1){
                    continue;
                }
                if(array[px][py] == 0){
                    array[px][py] = dis;
                    queue.add(new Pair(px, py, dis));
                }
            }  
        }
        System.out.println(array[n-1][m-1]);
    }
    
    static class Pair{
        int x;
        int y;
        int distance;
        public Pair(int x, int y, int distance){
            this.x = x;
            this.y = y;
            this.distance = distance;
        }
    }
}