프로그래머스 Lv.2 게임 맵 최단거리 [Java]

1. 문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/1844

2. 문제 해설

최단거리를 찾는 대표적인 문제이다. 이렇게 최단거리를 찾아야하는 문제는 bfs를 이용하여서 푸는 것이 편하다.
처음에 풀었을 때는 dfs도 간만에 구현해볼 겸하고 dfs로 풀었다가 시간 초과로 효율성 테스트를 통과하지 못했다.
bfs는 목적지에 도착했을 때, 최단거리로 방문하는 것이 보장되지만 dfs는 모든 경우의 수를 다 보기 때문에 더 오랜 시간이 걸리기 때문이다.

3. 코드 보기

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

class Solution {
    class Point {
        int r, c;

        public Point(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }

    int[] dr = {0, 1, 0, -1};
    int[] dc = {1, 0, -1, 0};
    int answer = Integer.MAX_VALUE;

    public int solution(int[][] maps) {
        int[][] dis = new int[maps.length][maps[0].length];
        for (int i = 0; i < maps.length; i++) {
            Arrays.fill(dis[i], -1);
        }

        answer = bfs(maps, dis, 0);

        if (answer == Integer.MAX_VALUE) {
            answer = -1;
        }

        return answer;
    }

    private int bfs(int[][] maps, int[][] dis, int cnt) {
        Queue<Point> q = new LinkedList<>();
        q.add(new Point(0, 0));
        dis[0][0] = 0;

        while (!q.isEmpty()) {
            Point cur = q.poll();
            cnt++;

            if (cur.r == maps.length - 1 && cur.c == maps[0].length - 1) {
                return dis[cur.r][cur.c] + 1;
            }

            for (int i = 0; i < 4; i++) {
                int nr = cur.r + dr[i];
                int nc = cur.c + dc[i];

                if (nr < 0 || nc < 0 || nr >= maps.length || nc >= maps[0].length || maps[nr][nc] == 0 || dis[nr][nc] >= 0) {
                    continue;
                }

                q.add(new Point(nr, nc));
                dis[nr][nc] = dis[cur.r][cur.c] + 1;
            }
        }

        return Integer.MAX_VALUE;
    }
}