プログラマーLV.2ゲームマップ最短距離


1.問題リンク


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

2.解答

  • の位置を記録するためのPairクラスが発表された.
    -yは縦で、xは横です.
  • アクセス配列記録移動距離.
  • BFSを用いて最短距離を求める.
  • 3.コード

    import java.util.ArrayDeque;
    import java.util.Queue;
    
    public class Solution {
        static class Pair {
            int y, x;
    
            public Pair(int y, int x) {
                super();
                this.y = y;
                this.x = x;
            }
    
        }
    
        static int[][] visit; // 방문한 경우 비용을 기록
        static int[] dirY = {0, 0, 1, -1};
        static int[] dirX = {1, -1, 0, 0};
    
        public int solution(int[][] maps) {
            int N = maps.length;
            int M = maps[0].length;
            visit = new int[N][M];
    
            // BFS
            Queue<Pair> q = new ArrayDeque<>();
            // 시작점 큐에 삽임 & 방문 처리
            q.add(new Pair(0, 0));
            visit[0][0] = 1;
    
            while (!q.isEmpty()) {
                Pair now = q.poll();
                for (int i = 0; i < 4; i++) {
                    int yy = now.y + dirY[i];
                    int xx = now.x + dirX[i];
                    if (yy < 0 || xx < 0 || yy >= N || xx >= M || visit[yy][xx] != 0 || maps[yy][xx] == 0)
                        continue;
                    // 다음 위치의 비용 = 현재 위치에 닿는 비용 + 1
                    visit[yy][xx] = visit[now.y][now.x] + 1;
                    q.add(new Pair(yy, xx));
                }
            }
    
            int answer = -1;
            // 도착했다면?
            if (visit[N - 1][M - 1] != 0) {
                answer = visit[N - 1][M - 1];
            }
            return answer;
        }
    }

    4.採点結果



    5.感じ

  • 基本BFS問題