[백준(Baekjoon)] 2178. 미로 탐색 (java, BFS)

안녕하세요.! 오늘은 백준의 2178. 미로 탐색 문제를 풀어보려고 합니다.

문제 링크

https://www.acmicpc.net/problem/2178

전체 코드

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

public class Main {
    private static int[][] map;
    
    private static int N;
    private static int M;
    
    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());
        
        map = new int[N][M];
        
        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), "");
            char[] line = st.nextToken().toCharArray();
            
            for(int j = 0; j < M; j++) {
                map[i][j] = line[j] - '0';
            }
        }
        
        bfs(0,0);
        
        System.out.println(map[N-1][M-1]);
    }
    
    private static void bfs(int sr, int sc) {
        int[] dr = {-1, 1, 0, 0};
        int[] dc = {0, 0, -1, 1};
        
        boolean[][] visited = new boolean[N][M];
        Queue<Miro> q = new LinkedList<>();
        
        q.offer(new Miro(sr, sc));
        visited[sr][sc] = true;
        
        while(!q.isEmpty()) {
            Miro miro = q.poll();
            
            for(int d = 0; d < 4; d++) {
                int nr = miro.r + dr[d];
                int nc = miro.c + dc[d];
                
                if(nr < 0 || nc < 0 || nr >= N || nc >= M) {
                    continue;
                }
                
                if(visited[nr][nc] == true || map[nr][nc] == 0) {
                    continue;
                }
                
                q.add(new Miro(nr, nc));
                //생각하지 못해서 틀렸던 부분, 이렇게 코드 안짜고 cnt++로 짰었음
                map[nr][nc] = map[miro.r][miro.c] + 1;
                visited[nr][nc] = true;
            }
        }
    }
}
              
class Miro {
    int r;
    int c;
    
    Miro(int r, int c) {
        this.r = r;
        this.c = c;
    }
}

느낀점

처음으로 인터넷을 찾아보지 않고 혼자 BFS를 구현해봤다.! 그렇지만 구현까지였고, 답은 틀렸다. 현재 탐색한 map에 이전 map 값을 더하는 방식을 생각하지 못했고, 그냥 cnt를 하나씩 더하는 방식으로 풀어서 틀렸다.
cnt를 하나씩 더하는 방식으로 문제를 풀었더니 case1에서 자꾸 답이 17이 나왔다. 이유를 알지 못했고, 인터넷을 찾아본 결과 최단거리를 구하는 경우에는 현재 map에 이전까지 탐색된 map값을 더해줘야 한다는 사실을 알았다.
새로운 구현방법을 알았으니 얼른 다른문제에 적용해보러 가야겠다.!

[참고한 곳]
https://wiselog.tistory.com/163