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

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

문제

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

문제 분석

조건

• n*m 사이즈로 주어진 맵에서 0,0(문제에선 1,1) 좌표에서 n-1, m-1(n, m) 좌표로 이동하는데 최단 거리를 구하는 문제이다.

풀이방법

• 최단거리를 구하는 문제이므로 bfs의 가장 기본적인 문제이다.
• 거쳐간 땅의 수를 구해야하는 문제이므로 간단하게 좌표와 카운트를 변수로 가지는 Node 클래스를 만들어 문제를 해결했다.
• 처음 있던 위치부터 카운트해야하므로 초기 카운트가 1부터 시작한다.

코드

import java.util.*;

class Solution {
    public int solution(int[][] maps) {
        int[][] dr = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        int goalR = maps.length;
        int goalC = maps[0].length;
        boolean[][] visited = new boolean[goalR][goalC];
        goalR--;
        goalC--;

        Deque<Node> que = new ArrayDeque<>();
        que.add(new Node(0, 0, 1));
        visited[0][0] = true;

        while (!que.isEmpty()) {
            Node now = que.pop();
            if (now.getR() == goalR && now.getC() == goalC) {
                return now.getCount();
            }
            for (int[] d : dr) {
                int nextR = now.getR() + d[0];
                int nextC = now.getC() + d[1];
                if (nextR >= 0 && nextR <= goalR && nextC >= 0 && nextC <= goalC) {
                    if (maps[nextR][nextC] == 0 || visited[nextR][nextC]) {
                        continue;
                    }
                    visited[nextR][nextC] = true;
                    que.add(new Node(nextR, nextC, now.getCount() + 1));
                }
            }
        }
        return -1;
    }
}

class Node {
    private int r;
    private int c;
    private int count;

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

    public int getR() {
        return r;
    }

    public int getC() {
        return c;
    }

    public int getCount() {
        return count;
    }
}

결과