[프로그래머스] 게임 맵 최단거리(JAVA)

코딩테스트연습(DFS,BFS) - 게임 맵 최단거리

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

프로그래머스

문제 설명

왼쪽 최상단에서 출발하여 오른쪽 최하단으로 이동할 수 있는 최단거리를 구하는 문제이다.

벽이 있는 자리는 0으로 나타내고 없는 자리는 1로 나타낸다.

목적지까지 이동할 수 없을 때는 -1을 출력한다.

---

문제 풀이

생각 과정

최단경로를 구하는 문제이므로 BFS로 풀기로 생각했고 

우선순위 큐를 활용하여 구현했다.

우선순위큐를 사용하면 모든 경우를 구하지 않더라도 가장 적은 이동 수부터 뽑아와서 계산하기 때문에

목적지에 도달하면 그것이 바로 최단거리이므로 탐색을 종료해도 된다.

 

방법은 큐에 각 좌표와 해당좌표로 이동하기 위한 칸의 개수를 저장한다.

우선순위는 칸의 개수에 따라 지정되게 설정한다.

 

다음으로 큐에서 좌표를 꺼내어 상하좌우 4방향으로 이동시키며 

이동한 좌표와 증가한 이동횟수를 큐에 저장해준다.

목적지에 도착하면 이동횟수를 출력하고 종료한다.

 

주의할 점은 목적지에 도착하는 것이 불가능한 경우 같은 경로를 계속하여 반복할 수 있으므로

방문체크를 할 배열을 선언해줘야한다.

 

구현

import java.util.*;

class Solution {
    public int solution(int[][] maps) {
        int[] dy = new int[]{0, 0, 1, -1};	// 4가지 방향
        int[] dx = new int[]{1, -1, 0, 0};
        boolean[][] visit = new boolean[maps.length][maps[0].length];	// 방문체크할 배열
        int answer = -1;
        Queue<Node> q = new PriorityQueue<>();
        q.add(new Node(0, 0, 1));
        while (!q.isEmpty()) {
            Node cur = q.poll();
            if (cur.y == maps.length - 1 && cur.x == maps[0].length - 1) {	// 목적지 도달
                answer = cur.cnt;
                break;
            }
            for (int i = 0; i < 4; i++) {
                int ny = cur.y + dy[i];
                int nx = cur.x + dx[i];
                if (ny >= maps.length || ny < 0 || nx >= maps[0].length || nx < 0 || maps[ny][nx] == 0 || visit[ny][nx]) continue;	// 경계를 넘어가거나 이미 방문한 곳
                visit[ny][nx] = true;
                q.add(new Node(ny, nx, cur.cnt + 1));
            }
        }
        return answer;
    }
}

class Node implements Comparable<Node> {
    int y;
    int x;
    int cnt;

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

    @Override
    public int compareTo(Node o) {
        return this.cnt - o.cnt;
    }
}

반성

문제예시에 정사각형으로 되어있어서 모든 입력이 정사각형인줄 알았으나 그렇지 않았다...

설명을 제대로 읽자..좀...