[BOJ_22944] 죽음의 비

설명

---

https://github.com/tony9402/baekjoon/blob/main/solution/backtracking/22944/main.py

위 솔루션을 참고하여 문제를 풀었다.

 

계속해서 시간 초과가 나서 솔루션을 보게 되었는데 아래와 같은 결과로 풀 수 있었다.

 

결국 우리는 갈 수 있는 거리 이내에 체력 + 내구도가 버텨주면 된다. 따라서, 아래와 같이

dist2 - 1 >= health + durability

(U 위치에서도 죽음의 비가 내린다.)

이 거리에서만 도달 가능하다면 지금 들고 있는 우산으로 갈 수 있는 거리가 나오고 이때, 만일 현재 우산의 내구도가 거리 보다 크다면 조건에 의해서 죽음의 비를 피하고 해당 우산은 버린 뒤 다시 새로운 우산을 집어들고 출발하게 된다.

 

이와 달리, 거리 조건이 지금 들고 있는 우산의 내구도 보다 작다면 체력이 일정량 깍이는 것을 감안해야한다. 따라서, 이런식으로 처리가 들어가게 되어서 최대한 적은량의 방문을 통하여 메서드를 끝낼 수 있게 된다.

 

그리고, 아래 부분은 재귀를 돌았을때도 마찬가지 이지만 현재 위치에서 End Point로 바로 갈 수 있는 거리내에 내 체력 및 내구도가 버텨준다면 바로가고 재귀를 끝내면 된다. 이때의 경우를 위해서 만들어진 것이다.

int dist = Math.abs(end[0] - y) + Math.abs(end[1] - x);

그럼 위 경우들을 모두 조합하면 U가 1,2,3 이 있을때 각각의 U를 선택해서 나가는 순열처럼 보일 수 있을 것이다. 이때, 아무것도 선택하지 않아도 답이 나오는 경우도 있을 것이고 start->1->2->end 가 최적인 것 처럼 보일 수 있을 것이다.

 

다 만들어서 나열하면 결국 일반적인 형식의 백트래킹 조건이 완성되었다.

 

코드

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class BOJ_22944 {
    static int n, h, d;
    static char[][] map;
    static boolean[][] visited;
    static ArrayList<int[]> umbs;
    static int[] start;
    static int[] end;
    static int INF = 99999999;
    static int answer = INF;
    static int[] dy = {0, 0, -1, 1};
    static int[] dx = {-1, 1, 0, 0};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        h = Integer.parseInt(input[1]);
        d = Integer.parseInt(input[2]);

        visited = new boolean[n][n];
        umbs = new ArrayList<>();
        map = new char[n][n];

        for (int i = 0; i < n; i++) {
            String line = br.readLine();
            for (int j = 0; j < n; j++) {
                map[i][j] = line.charAt(j);
                if (map[i][j] == 'U') {
                    umbs.add(new int[]{i, j});
                } else if (map[i][j] == 'S') {
                    start = new int[]{i, j};
                } else if (map[i][j] == 'E') {
                    end = new int[]{i, j};
                }
            }
        }

        dfs(start[0], start[1], h, 0, 0);

        if (answer == INF) {
            System.out.println(-1);
        } else {
            System.out.println(answer);
        }
    }

    static void dfs(int y, int x, int health, int durability, int cnt) {
        int dist = Math.abs(end[0] - y) + Math.abs(end[1] - x);
        if (dist <= health + durability) {
            answer = Math.min(answer, cnt + dist);
            return;
        } else {
            for (int[] umb : umbs) {
                int uy = umb[0];
                int ux = umb[1];
                if (visited[uy][ux]) continue;
                int dist2 = Math.abs(uy - y) + Math.abs(ux - x);
                if (dist2 - 1 >= health + durability) continue;
                visited[uy][ux] = true;
                if (dist2 <= durability) {
                    dfs(uy, ux, health, d, cnt + dist2);
                } else {
                    dfs(uy, ux, health + durability - dist2, d, cnt + dist2);
                }
                visited[uy][ux] = false;
            }
        }
    }
}