[백준 #2178] 미로 탐색

백준 #2178 미로 탐색

백준 #2178

---

문제 설명👩‍🏫

(1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구해라

입출력 예

입력
4 6
101111
101010
101011
111011

출력
15

---

내 코드💻

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

public class Main {
    static int []dicX = {0,0,1,-1};
    static int []dicY = {1,-1,0,0};
    static int[][] list;
    static int[][] visited;
    static int h,w,nowX,nowY;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        StringTokenizer st = new StringTokenizer(str, " ");

        h = Integer.parseInt(st.nextToken());
        w = Integer.parseInt(st.nextToken());

        list = new int[h][w];
        visited = new int[h][w];
        for(int i=0;i<h;i++){
            str = br.readLine();
            int j = 0;
            for(char ch : str.toCharArray()) {
                list[i][j] = Integer.parseInt(String.valueOf(ch));
                j++;
            }
        }

        bfs(0,0);

        System.out.println(list[h-1][w-1]);


    }
    static void bfs(int x, int y){
        Queue <int[]> que = new LinkedList<>();

        que.add(new int[]{x,y});
        while(!que.isEmpty()) {
            int[]tmp = que.poll();
            for (int i = 0; i < 4; i++) {
                nowX = tmp[0] + dicX[i];
                nowY = tmp[1] + dicY[i];

                if(checking(nowX,nowY) && visited[nowX][nowY] == 0 && list[nowX][nowY]==1){
                    visited[nowX][nowY] = 1;
                    que.add(new int[]{nowX,nowY});
                    list[nowX][nowY] = list[tmp[0]][tmp[1]]+1;
                }
            }
        }
    }

    static boolean checking(int x, int y){
        return (x>=0 && x<h && y>=0 && y<w);
    }
}

---

설명💡

이번 문제는 bfs를 사용하는 문제였다. 좌표 0,0 부터 queue에 넣고, queue에 들어있는 좌표를 기준으로 상하좌우 4방향을 각각 반복하면서 1이라면 다시 queue에 넣고를 반복했다.
현재 좌표는 바로 전 좌표에 +1을 해가면서 경로를 표시하고, 마지막엔 배열의 n,m 위치에 있는 값을 리턴한다.

---

조금 실수한 부분은

int max = 0;
        for(int i=0;i<h;i++){
            for(int j=0;j<w;j++){
                max = Math.max(list[i][j],max);
            }
        }

이렇게 쓰면, n,m 값이 아닌 최댓값이 나오기 때문에 이상하다는 점을 조금 늦게 파악했다.

---

느낀 점 및 궁금한 점🍀

bfs 어렵다.. 아직 헷갈리는 부분이 많다..