문제

인성이는 인싸가 되기 위해서 인싸트 특별과정에 참가했다. 훈련 첫날 인성이는 험난한 미로에서 목적지에 도달해야 하는 훈련을 받고 있다. 제한 시간 안에 미로를 통과하지 못하면 명기 교관 님에게 욕을 듣기에 인성이는 최선을 다해 미로를 통과하려고 한다.

미로는 가로 길이 W, 세로 길이 H의 격자 형태를 가지며, 인성이는 한 번에 격자 상의 상, 하, 좌, 우로 한칸 씩 움직일 수 있다. 매 이동이 완료될 시에 인성이의 남은 힘은 1씩 감소하고, 남은 힘이 0이하인 경우에는 더 이상 움직이지 못하게 된다.

미로의 각 격자에는 장애물이 있는데, 각각의 장애물은 높이 정보를 가지고 있다. 장애물이 없는 위치는 전부 높이가 0 이다. 인성이가 이동할 때, 현재 위치보다 이동할 위치의 높이가 더 낮으면 아무런 제약을 갖지 않고 이동할 수 있다. 더 높은 곳으로 이동할 때는 점프를 할 수 있는데, 점프해야 하는 높이는 (이동할 곳의 높이 - 현재 위치한 곳의 높이) 이다. 이때 남아있는 힘이 점프해야 하는 높이보다 크거나 같으면 이동할 수 있고, 그렇지 않으면 이동하지 못한다.

인성이는 신체적 한계를 극복하고 무사히 목적지에 도달해서 명기 교관님의 욕설을 듣지 않을 수 있을까?

입력

첫째 줄에 테스트 케이스 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다.

첫째 줄에 미로의 세로길이 H, 가로길이 W, 장애물의 개수 O, 초기 힘 F, 출발지의 좌표 정보 Xs(행), Ys(열)목적지의 좌표정보 Xe(행), Ye(열) 가 주어진다.

둘째 줄부터 O개의 줄에 장애물의 좌표 정보 X(행), Y(열) 와 높이 정보 L이 주어진다. 모든 장애물은 서로 다른 위치에 존재한다.

출력

T개의 줄에 인성이가 목적지에 도착할 수 있을 때 "잘했어!!", 목적지에 도착할 수 없을 때 "인성 문제있어??" 를 출력한다.

import java.io.*;
import java.util.*;
public class Main {
    static int w, h, O, F, sX, sY;
    static int[][] arr;
    static boolean[][] visited;
    static int[] dx = { -1, 1, 0, 0 };
    static int[] dy = { 0, 0, 1, -1 };
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        int T = Integer.parseInt(st.nextToken());
        for (int t = 0; t < T; t++) {
            st = new StringTokenizer(br.readLine());
            h = Integer.parseInt(st.nextToken());
            w = Integer.parseInt(st.nextToken());
            O = Integer.parseInt(st.nextToken());
            F = Integer.parseInt(st.nextToken());
            sX = Integer.parseInt(st.nextToken())-1;
            sY = Integer.parseInt(st.nextToken())-1;
            int eX = Integer.parseInt(st.nextToken())-1;
            int eY = Integer.parseInt(st.nextToken())-1;
            arr = new int[h][w];
            for (int i = 0; i < O; i++) {
                st = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st.nextToken())-1;
                int y = Integer.parseInt(st.nextToken())-1;
                int b = Integer.parseInt(st.nextToken());
                arr[x][y] = b;
            }

         System.out.println(BFS(eX, eY) >= 0 ? "잘했어!!" : "인성 문제있어??");
        }
    }

    public static int BFS(int eX, int eY) {
        visited = new boolean[h][w];
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(sX, sY, F));
        visited[sX][sY] = true;
        while(!q.isEmpty()) {
            Node n = q.poll();
            if (n.x == eX && n.y == eY) {
                return n.force;
            }
            for (int i = 0; i < 4; i++) {
                int nx = n.x + dx[i];
                int ny = n.y + dy[i];
                if (nx < 0 || ny < 0 || nx >= h || ny >= w)
                    continue;
                if (visited[nx][ny])
                    continue;
                if (arr[nx][ny] > arr[n.x][n.y]) { // 다음 칸이 더 높을 경우
                    if (Math.abs(arr[nx][ny] - arr[n.x][n.y]) <= n.force) {
                        q.add(new Node(nx, ny, n.force - 1));
                    }
                } else { // 다음 칸이 낮을 경우
                    q.add(new Node(nx, ny, n.force-1));
                }
                visited[nx][ny] = true;
            }
        }
        return -1;


    }
}

class Node {
    int x, y, force;
    Node (int x, int y, int force) {
        this.x = x;
        this.y = y;
        this.force = force;
    }
}

• 예제 입력을 보고 맵은 3x3인데 왜 3x7이 나오지하고 생각했는데 장애물 개수(x, y, 장애물 난이도)였다.
• 다음 칸이 현재 칸보다 높을 경우와 아닌 경우를 나누어서 로직 구성.
• 다음 칸으로 이동할 때마다 force-1 적용.
• 성공하면 force가 아직 자연수라는 의미로 "잘했어!!"출력.
• 출력 부분 로직을 BFS(eX, eY) > 0로 작성해서 97%에서 멈춤. 문제를 보면 남은 힘이 0이하인 경우 더 이상 못움직인다고 작성되어 있다.