[프로그래머스] 게임 맵 최단거리 - Java

문제 설명

 

프로그래머스

 

접근 방법

해당 문제는 2차원 그래프 상에 특정 출발 지점에서 특정 도착 지점까지 가는 최단 경로를 구하는 문제로서 BFS(너비 우선 탐색)를 이용하여 해결할 수 있었습니다.

 

도착 지점은 (0, 0)으로, 출발 지점은 (n, m)으로 정해져있으므로, 처음 노드의 좌표를 (0, 0)으로 초기화 해준 후 이를 기점으로 동, 서, 남, 북 방향으로 너비 우선 탐색하도록 했습니다. 이때 탐색의 제외 대상으로는 맵을 이탈하는 경우, 기존에 방문했었던 좌표, 벽인 경우가 있습니다.

 

탐색 시 도착 지점 (n, m)에 도달한 경우 현재 노드에서 저장하고 현재 거리 값에 1을 더하여 반환하도록 합니다. 해당 탐색은 너비 우선 탐색이므로 가장 먼저 도착 지점에 도달한 노드가 최단 거리일 수밖에 없습니다. 만일 깊이 우선 탐색을 했다면 너비 우선 탐색 보다는 좀 더 까다롭게 최단 거리를 구할 수 있을 것으로 생각됩니다.

 

 

전체 소스 코드

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

class Solution {

    int[] dx = {0, 0, 1, -1}, dy = {1, -1 , 0 ,0};

    static class Node {
        int x;
        int y;
        int distance;

        public Node(int x, int y, int distance) {
            this.x = x;
            this.y = y;
            this.distance = distance;
        }
    }

    public int solution(int[][] maps) {
        int answer = -1;

        int height = maps.length, width = maps[0].length;

        boolean[][] visited = new boolean[height][width];

        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(0, 0, 1));
        visited[0][0] = true;

        int nx, ny;

        while (!queue.isEmpty()) {

            Node node = queue.poll();

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

                if (nx < 0 || nx > height - 1 || ny < 0 || ny > width - 1 || visited[nx][ny] || maps[nx][ny] == 0) {
                    continue;
                }

                if (nx == height - 1 && ny == width - 1) {
                    return node.distance + 1;
                }

                visited[nx][ny] = true;
                queue.add(new Node(nx, ny, node.distance + 1));
            }
        }


        return answer;
    }
}

 

 

참고자료

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