[정올 1008] 경로찾기(find route) - JAVA

문제 링크

문제 정의

• $N*N$의 격자판이 존재
• 이동까지 시간 제약 $t$가 주어짐
  • 상/하/좌/우로 1칸 이동하는데 1시간 소요
  • $t$는 시간 단위
• 각 칸에는 $-2$보다 크고 $10,000$이하의 숫자가 주어짐
  • $0$: 건물
  • $-1$: 출발점
  • $-2$: 도착 지점
  • 나머지 양수: 일사량

출발 지점에서부터 도착 지점까지 $t$시간 이내에 도달하는 경로 중 일사량의 최솟값을 출력
(경로가 없는 경우는 -1 출력)

---

접근 방법

이 문제에서는 두 가지를 고려해야 합니다.

• 시간 내에 이동 가능한 경로
• 일사량의 최솟값

하지만 이동 가능한 경로를 모두 탐색하면 TLE에 걸릴 가능성이 높습니다.
그래서 저는 두 가지 가지치기 방식을 적용했습니다.

도착 지점으로부터의 거리 배열인 $dist$를 정의해 가지치기 하기

어떤 경로의 일사량이 최소값이 될지 모르기 때문에 모든 경로를 탐색하는 방식에서
거리 배열인 dist를 활용해서
현재 위치로부터 도착 지점까지의 최단 경로로 이동할 때 걸리는 시간을 저장해놓고

현재 위치까지 도달 시간 + 도착 지점까지의 최단 경로 > t

위와 같은 조건을 만족하는 경우
시간 내에 이동이 불가능한 경로로 판단해 가지치기를 수행하는 방식을 구현했습니다.

그래서 setDist라는 메서드를 구현해
초기화 작업에서 dist 배열도 초기화하도록 구현했습니다.

현재 칸까지 이동했을 때의 최소 일사량을 기록하는 $ins$ 배열을 선언

이 문제를 격자판 다익스트라로 인식했습니다.
일사량을 거리로 판별한다면 다익스트라와 같이 문제를 해결할 수 있을 것이라고 생각했습니다.
즉 ins 배열은 다익스트라에서 dist 배열과 같은 역할을 한다고 볼 수 있습니다.

그래서 두 가지를 고려해서 로직을 설계한다면
ArrayDeque를 사용하는 다익스트라 같은 BFS?
로직을 구현하게 되어 문제를 해결할 수 있습니다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.StringTokenizer;


class Node {
    int y;
    int x;
    int c;
    int w;

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

public class Main {
    static final int MAX = Integer.MAX_VALUE;
    static StringTokenizer st;
    static int[] dy = {-1, 0, 1, 0};
    static int[] dx = {0, -1, 0, 1};
    static int[][] area;
    static int[][] dist;
    static int[][] ins;
    static int n;
    static int t;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        t = Integer.parseInt(st.nextToken());
        area = new int[n][n];
        dist = new int[n][n];
        ins = new int[n][n];

        int sy = 0;
        int sx = 0;
        int ey = 0;
        int ex = 0;
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            Arrays.fill(ins[i], MAX);
            for (int j = 0; j < n; j++) {
                area[i][j] = Integer.parseInt(st.nextToken());
                if(area[i][j] == -1) {
                    sy = i;
                    sx = j;
                }
                else if (area[i][j] == -2) {
                    ey = i;
                    ex = j;
                }
            }
        }

        setDist(ey, ex);
        System.out.println(bfs(sy, sx, ey, ex));
    }

    private static int bfs(int sy, int sx, int ey, int ex) {
        ArrayDeque<Node> q = new ArrayDeque<>();
        q.offer(new Node(sy, sx, 0, 0));
        ins[sy][sx] = 0;

        while (!q.isEmpty()) {
            Node node = q.poll();
            int y = node.y;
            int x = node.x;
            int c = node.c;
            int w = node.w;

            if (c + dist[y][x] > t || ins[y][x] < w) continue;

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

                if (ny == ey && nx == ex && c + 1 <= t) {
                    ins[ny][nx] = Math.min(ins[ny][nx], w);
                    continue;
                }

                if (inbound(ny, nx) && area[ny][nx] != 0 && ins[ny][nx] > w + area[ny][nx]) {
                    ins[ny][nx] = w + area[ny][nx];
                    q.offer(new Node(ny, nx, c + 1, ins[ny][nx]));
                }
            }
        }

        return ins[ey][ex] == MAX ? -1 : ins[ey][ex];
    }

    static void setDist(int ey, int ex) {
        ArrayDeque<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{ey, ex, 0});
        dist[ey][ex] = -1;

        while (!q.isEmpty()) {
            int[] node = q.poll();
            int y = node[0];
            int x = node[1];
            int z = node[2];

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

                if (inbound(ny, nx) && area[ny][nx] != 0 && dist[ny][nx] == 0) {
                    dist[ny][nx] = z + 1;
                    q.offer(new int[]{ny, nx, z+1});
                }
            }
        }

        dist[ey][ex] = 0;
    }

    static boolean inbound(int y, int x) {
        return 0 <= y && y < n && 0 <= x && x < n;
    }
}