백준 - 2178

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Main {
    static int[][] dist = {
            {-1,0},{1,0},{0,-1},{0,1}};
    static int N;
    static int M;
    static boolean[][] maze;
    static boolean[][] visited;
    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());

        maze = new boolean[N][M];
        for(int i = 0; i < N; i++){
            String s = br.readLine();
            for(int j = 0; j < M; j++){
                maze[i][j] = ( (s.charAt(j) - '1' == 0));
            }
        }
        visited = new boolean[N][M];
        System.out.println(bfs(0,0,2));
    }
    static int bfs(int i, int j, int count){
        visited[i][j] = true;
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[] {i,j,count});

        while(!q.isEmpty()) {
            int[] a = q.poll();
            int r = a[0]; int c = a[1]; int cnt = a[2];
            for (int d = 0; d < 4; d++) {
                int nr = r + dist[d][0];
                int nc = c + dist[d][1];

                if (nr >= 0 && nc >= 0 && nr < N && nc < M
                        && !visited[nr][nc] && maze[nr][nc]) {
                    if(nr == N-1 && nc == M -1) return cnt++;
                    visited[nr][nc] = true;
                    q.add(new int[] {nr,nc,cnt+1});
                }
            }
        }
        return -1;
    }
}

풀이과정 및 리뷰

1. 1 인 경우 true 값을 가지는 boolean[][] maze , 방문여부 확인할 boolean[][] visited 생성
2. 상하좌우로만 인접한 경우에 해당해 전진할 수 있으므로 4방향 배열 생성
3. r, c, count를 인자로 받는 bfs 메서드 선언
   • (r,c,count)배열을 큐에 저장 → 꺼내서 주위 4방향 탐색해 maze[nr][nc] = true 라면 방문체크 및 큐에 다시 넣어서 큐가 빌 때까지 순회하도록 함
     
4. 처음과 끝점도 카운트에 포함되므로, 첫인자로 0,0,2를 넘긴다.

중대한 오류와 보완점

System.out.println(bfs(0,0,2)); 로 시작할때 count 2로 넘김

→ 잘 생각해보면, 끝점은 bfs메서드 안에서 지나면서 count+1될 것이므로 (0,0,1)을 인자로 넘겼어야 했음.

bfs 메서드 안의 if(nr == N-1 && nc == M -1) return cnt++; 에서 내 의도는 return cnt+1 이었지만, 후위연산자여서 cnt값을 반환하고 cnt+1은 버려지므로 이 두개의 잘못된 코드가 맞물려 결과적으로는 맞았지만,

올바르게 고치면 System.out.println(bfs(0,0,1)); , if(nr == N-1 && nc == M -1) return cnt+1; 로 적었어야 했다.

요약

오류 : 시작점부터 cnt = 2로 시작점과 끝점을 모두 카운트 한채로 bfs 돌았음 + 도착점에서 후위연산자 착각해서 결과적으로 cnt+1 이 아닌 cnt 가 반환됨. → 시작에서 1크게, 끝에서 1작게 코드를 작성해서 아다리는 맞았지만 내 의도와는 맞지 않았음

수정 : 시작점에서 cnt = 1 로 시작해서 시작점만 밟은 채로 순회 시작 + 도착점 도달시 cnt+1 되게 수정

최종 수정본

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Main {
    static int[][] dist = {
            {-1,0},{1,0},{0,-1},{0,1}};
    static int N;
    static int M;
    static boolean[][] maze;
    static boolean[][] visited;
    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());

        maze = new boolean[N][M];
        for(int i = 0; i < N; i++){
            String s = br.readLine();
            for(int j = 0; j < M; j++){
                maze[i][j] = ( (s.charAt(j) - '1' == 0));
            }
        }
        visited = new boolean[N][M];
        System.out.println(bfs(0,0,1));
    }
    static int bfs(int i, int j, int count){
        visited[i][j] = true;
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[] {i,j,count});

        while(!q.isEmpty()) {
            int[] a = q.poll();
            int r = a[0]; int c = a[1]; int cnt = a[2];
            for (int d = 0; d < 4; d++) {
                int nr = r + dist[d][0];
                int nc = c + dist[d][1];

                if (nr >= 0 && nc >= 0 && nr < N && nc < M
                        && !visited[nr][nc] && maze[nr][nc]) {
                    if(nr == N-1 && nc == M -1) return cnt + 1;
                    visited[nr][nc] = true;
                    q.add(new int[] {nr,nc,cnt+1});
                }
            }
        }
        return -1;
    }
}