문제

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

코드

public class Main {
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static boolean[][] check;
    static int[][] arr;
    static int N;
    static int M;

    public static void main(String[] args) throws IOException, InterruptedException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        check = new boolean[N][M];
        arr = new int[N][M];

        for (int i = 0; i < N; i++) {
            char[] line = br.readLine().toCharArray();
            for (int j = 0; j < M; j++) {
                arr[i][j] = line[j] - 48;
            }
        }

        check[0][0] = true;
        bfs(0, 0);
        System.out.println(arr[N - 1][M - 1]);
    }

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

        while (!q.isEmpty()) {
            int[] now = q.poll();
            int nowX = now[0];
            int nowY = now[1];

            for (int i = 0; i < 4; i++) {
                int mx = nowX + dx[i];
                int my = nowY + dy[i];

                if (mx < 0 || my < 0 || mx >= N || my >= M) continue;
                if (check[mx][my] || arr[mx][my] == 0) continue;

                q.add(new int[]{mx, my});
                arr[mx][my] = arr[nowX][nowY] + 1;
                check[mx][my] = true;
            }
        }
    }
}

생각

dfs로 풀다가 답이 잘 안나와서 답을 검색했다.
https://wiselog.tistory.com/163

dfs로도 가능하다고 한다.

bfs로 풀어야 풀리겠다는 생각은 했지만 어떻게 구현해야하는지 bfs로 했었던 풀이를 봐도 선뜻 안떠올라서 결국 답을 봤다.

이미 지나친 곳을 체크하는 것 까지는 했었다. 나는 count변수를 줘서 수를 셋는데 했는데 그렇게 했을 때 값이 제대로 안나왔었다. 디버깅을 해서 문제점을 알아는 냈는데 오전 시간이 끝나서 멈췄었다. 하지만 고쳤어도 타임오버였을 것이다.

bfs는 한 노드의 사방을 탐색하고 한칸 이동하면서 이전 칸의 수 +1 을 해준 값을 넣어주면된다.
이 때 check를 통해 밟았던 곳은 재 탐색하지 않기 때문에 그 위치의 값이 덮어질 우려도 없다.
쭉 진행하다 보면 우리의 목표인 (N, M) 위치를 지나치는 경우도 있지만 그 위치의 값은 변함이 없기 때문에 결국 (N, M) 위치의 값은 최소경로의 값이 저장된다.