게임 맵 최단거리

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

프로그래머스

 

 

소스코드

import java.util.ArrayDeque;

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

    int[] rx = new int[]{0, 0, -1, 1};
    int[] ry = new int[]{-1, 1, 0, 0};

    public int solution(int[][] maps) {
        ArrayDeque<Node> queue = new ArrayDeque<>();
        int dist[][] = new int[maps.length][maps[0].length];
        boolean visited[][] = new boolean[maps.length][maps[0].length];
        dist[0][0] = 1;
        visited[0][0] = true;

        queue.addLast(new Node(0, 0));
        while(!queue.isEmpty()) {
            Node node = queue.pollFirst();

            for (int i = 0; i < 4; i++) {
                int nr = node.r + rx[i];
                int nc = node.c + ry[i];

                if(nr < 0 || nc < 0 || nr >= maps.length || nc >= maps[0].length) continue; //범위 밖
                if(maps[nr][nc] == 0) continue; //벽
                if(visited[nr][nc]) continue; //이미 방문

                visited[nr][nc] = true;
                dist[nr][nc] = dist[node.r][node.c] + 1;
                queue.addLast(new Node(nr, nc));
            }
        }

        return dist[maps.length - 1][maps[0].length - 1] == 0 ? -1 : dist[maps.length - 1][maps[0].length - 1];
    }
}

 

 

해결방법

BFS를 이용하였다.