[Programmers / Level 2] 1844. 게임 맵 최단거리 (Java)

💡 Info

• 난이도: Lv2
  프로그래머스 링크: https://school.programmers.co.kr/learn/courses/30/lessons/1844
  풀이 링크(GitHub): hayannn/CodingTest_Java/프로그래머스/2/게임 맵 최단거리

입출력 조건

입출력 예시

문제 이해

• (ROR 게임) 상대 팀 진영에 도착하기 위해 지나가야 하는 칸 개수의 최솟값을 반환하는 문제
  • 상대 팀 진영에 도착하지 않으면, -1 반환

알고리즘

풀이 시간 : 25분

• BFS(너비 우선 탐색)로 최단 경로 탐색
• visited[x][y]에 시작점부터의 거리 누적
  • 상하좌우 4방향 이동(dx, dy)
• 도달 불가 시 -1

import java.util.*;

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

    public int solution(int[][] maps) {
        int n = maps.length;
        int m = maps[0].length;
        int[][] visited = new int[n][m];
        Queue<int[]> queue = new LinkedList<>();

        queue.add(new int[]{0, 0});
        visited[0][0] = 1;

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int x = cur[0], y = cur[1];

            if (x == n - 1 && y == m - 1) {
                return visited[x][y];
            }

            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i], ny = y + dy[i];
                if (nx >= 0 && nx < n && ny >= 0 && ny < m
                    && maps[nx][ny] == 1 && visited[nx][ny] == 0) {
                    visited[nx][ny] = visited[x][y] + 1;
                    queue.add(new int[]{nx, ny});
                }
            }
        }
        return -1;
    }
}

결과

✍️ 다른 풀이 - 휴리스틱 활용

• 각 노드를 g(n)+h(n) 우선순위로 확장
  • g : 시작부터의 실제 거리
  • h: 목표까지의 휴리스틱
• 휴리스틱 : 맨해튼 거리 사용 시 admissible 보장

import java.util.*;

class Node implements Comparable<Node> {
    int x, y, g, h;
    Node parent;
    Node(int x, int y, int g, int h, Node p) {
        this.x = x; this.y = y; this.g = g; this.h = h; this.parent = p;
    }
    int f() { return g + h; }
    @Override
    public int compareTo(Node o) {
        return Integer.compare(this.f(), o.f());
    }
}

public class Solution {
    static int[] dx = {-1,1,0,0}, dy = {0,0,-1,1};

    public int solution(int[][] maps) {
        int n = maps.length, m = maps[0].length;
        boolean[][] closed = new boolean[n][m];
        PriorityQueue<Node> open = new PriorityQueue<>();
        open.offer(new Node(0,0,1,heuristic(0,0,n-1,m-1), null));

        while (!open.isEmpty()) {
            Node curr = open.poll();
            if (closed[curr.x][curr.y]) continue;
            if (curr.x == n-1 && curr.y == m-1) return curr.g;
            closed[curr.x][curr.y] = true;

            for (int i = 0; i < 4; i++) {
                int nx = curr.x + dx[i], ny = curr.y + dy[i];
                if (nx<0||nx>=n||ny<0||ny>=m||maps[nx][ny]==0||closed[nx][ny]) continue;
                open.offer(new Node(nx, ny, curr.g+1, heuristic(nx,ny,n-1,m-1), curr));
            }
        }
        return -1;
    }

    private int heuristic(int x1, int y1, int x2, int y2) {
        // 맨해튼 거리
        return Math.abs(x1 - x2) + Math.abs(y1 - y2);
    }
}