[프로그래머스] 게임 맵 최단거리 자바 풀이

문제

https://school.programmers.co.kr/learn/courses/30/lessons/1844?language=java

풀이

틀린 풀이

DFS를 통해 문제를 먼저 풀었지만 효율성 테스트에서 모두 실패했다.

새로운 풀이

문제점

DFS는 다음과 같은 문제가 있기 때문에 이 문제를 해결하는 방법으로 적합하지 않다.

• 해가 없는 경로가 깊을 경우 탐색시간이 오래 걸릴 수 있다.
• 얻어진 해가 최단 경로가 된다는 보장이 없다.

따라서, BFS로 다시 문제를 풀었다.

또한 맨날 헷갈리는 부분이 다익스트라(PQ)를 사용할 것인지 인데, PQ의 경우 가중치가 다른 경우에 사용한다는 것을 다시 기억하자.

일반적인 방법의 BFS를 통해 문제를 해결할 수 있다.

코드

package com.company.programmers;

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

public class P4 {
    static int[] dy = new int[] {-1,1,0,0};
    static int[] dx = new int[] {0,0,-1,1};
    static int[][] map;
    static boolean[][] visited;
    static int min = Integer.MAX_VALUE;
    public int solution(int[][] maps) {
        map = maps;

        visited = new boolean[maps.length][maps[0].length];
        visited[0][0] = true;
        bfs();
        if (min == Integer.MAX_VALUE) min = -1;
        return min;
    }
    public static void bfs() {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{0,0,1});
        while (!queue.isEmpty()) {
            int[] val = queue.poll();

            if (val[0] == map.length - 1  && val[1] == map[0].length - 1) {
                min = Math.min(val[2], min);
                return;
            }
            for (int i = 0; i < 4; i++) {
                int ny = val[0] + dy[i];
                int nx = val[1] + dx[i];

                if (ny < 0 || nx < 0 || ny >= map.length || nx >= map[0].length) continue;
                if (visited[ny][nx]) continue;
                if (map[ny][nx] == 0) continue;
                visited[ny][nx] = true;
                queue.add(new int[] {ny,nx,val[2]+1});
            }
        }

    }
    public static void main(String[] args) {
        P4 p4 = new P4();
        p4.solution(new int[][] {{1,0,1,1,1}, {1,0,1,0,1}, {1,0,1,1,1}, {1,1,1,0,1}, {0,0,0,0,1}});

    }

}