프로그래머스 lv2 게임 맵 최단 거리

문제 링크

게임 맵 최단 거리

풀이

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

class Solution {
    public int solution(int[][] maps) {
        return bfs(maps);
    }

     public int bfs(int[][] maps) {
        int[] dy = {1, 0, -1, 0};
        int[] dx = {0, 1, 0, -1};
        int n = maps.length;
        int m = maps[0].length;

        boolean[][] visit = new boolean[n][m];
        int answer = Integer.MAX_VALUE;

        Queue<Pos> q = new LinkedList<Pos>();
        q.add(new Pos(0,0,1));
        while(!q.isEmpty()) {
            Pos temp = q.poll();

            if(temp.y == n-1 && temp.x == m-1) {
                answer = Math.min(answer, temp.cnt);
                continue;
            }

            for (int dir = 0; dir < 4; dir++) {
                int ny = dy[dir] + temp.y;
                int nx = dx[dir] + temp.x;

                if(ny < 0 || nx < 0 || ny >= n || nx >= m || visit[ny][nx]) continue;
                if(maps[ny][nx] == 0) continue;

                visit[ny][nx] = true;
                int cnt = temp.cnt + 1;
                q.add(new Pos(ny, nx, cnt));
            }
        }

        return answer == Integer.MAX_VALUE ? -1 : answer;
    }

    class Pos {
        int y, x, cnt;

        public Pos(int y, int x, int cnt) {
            this.y = y;
            this.x = x;
            this.cnt = cnt;
        }
    }
}

해설

• 시작위치에서 목적지까지 최단거리를 구하는 문제는 bfs로 풀어야한다.
• Queue를 선언하고, 해당 큐에 Position 객체를 넣는다.
• 한번 방문했다면, boolean 타입의 배열인 visit에 true로 표시한다.

소감

• 처음엔 dfs로 풀었다가 털리고, 최단거리는 bfs로 풀어야한다는 걸 깨닫고 bfs로 풀었으나 효율성에서 털렸다.
• 문제가 많다.