프로그래머스 LV.2 게임 맵 최단거리

프로그래머스 LV.2 게임 맵 최단거리

1. 문제 링크

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

코딩테스트 연습 - 게임 맵 최단거리

 

2. 문제 해결에 대한 아이디어

1. 위치를 기록하는데 사용할 Pair 클래스를 선언했다.
   - y 를 세로, x를 가로로 사용했다.
2. 방문 배열에는 이동 거리를 기록한다.
3. 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. 느낀 점

1. 기본적인 BFS 문제