[BOJ/Gold 4] 백준 22944 죽음의 비(C++)

문제 링크

https://www.acmicpc.net/problem/22944

22944번: 죽음의 비

 

 

문제

가로, 세로 길이가 N인 정사각형 격자가 있다. 해당 격자에는 두 곳을 제외한 모든 곳에 체력을 1씩 감소시키는 죽음의 비가 내리고 있다. 죽음의 비가 안내리는 곳은 현재 있는 위치와 안전지대라는 곳이다. 현재 있는 위치에도 곧 비가 내릴 예정이라 빨리 이 죽음의 비를 뚫고 안전지대로 이동해야한다.

다행히도 격자에는 죽음의 비를 잠시 막아주는 우산이 K개 존재한다. 우산에는 내구도 D라는 개념이 존재한다. 우산에 비를 맞으면 내구도가 1씩 감소하고, 내구도가 0이 되는 순간 우산은 사라진다. 문제에서 주어지는 우산의 내구도는 모두 D로 동일하다.

격자에서 이동을 할 때 다음과 같이 순서로 진행된다.

1. 상하좌우로 이동한다. 만약 이동할 곳이 격자 밖이라면 이동할 수 없다. 
2. 이동한 곳이 안전지대라면 반복을 종료한다.
3. 이동한 곳에 우산이 있다면 우산을 든다. 만약, 이동할 때부터 우산을 가지고 있다면 가지고 있는 우산을 버리고 새로운 우산으로 바꾼다.
   버린 우산은 더 이상 사용할 수 없다.
4. 죽음의 비를 맞았을 때, 우산을 가지고 있다면 우산의 내구도가 1이 감소하고 만약 우산을 가지고 있지 않는다면 체력이 1 감소한다.
5. 만약 우산의 내구도가 0이 되면 들고 있는 우산이 사라진다.
6. 만약 체력이 0이 되면 죽는다...
7. 아직 체력이 남았다면 안전지대까지 위 과정을 반복한다.

현재 있는 위치에서 안전지대로 얼마나 빠르게 이동할 수 있는지 구해주자.

입력

첫 번째 줄에 정사각형 격자의 한변의 길이인 N와 현재 체력 H, 우산의 내구도 D가 공백으로 구분되어 주어진다.

다음 N개의 줄에는 정사각형 격자의 정보가 N개의 문자로 붙어서 주어진다. 이때 주어지는 문자는 우산은 "U", 현재 있는 위치 "S", 안전지대 "E", 빈 칸 "."만 존재한다. 현재 있는 위치 "S"와 안전지대 "E"는 반드시 1개 존재한다.

출력

안전지대로 이동할 때 최소 이동 횟수를 출력한다. 만약 안전지대로 이동하지 못하는 경우에는 -1을 출력한다.

제한

•  4 ≤ N ≤ 500
•  0 ≤ K ≤ 10
•  1 ≤ H ≤ 10,000
•  1 ≤ D ≤ 5,000
• 주어지는 모든 수는 정수이다.

예제 입력 1

4 10 4
S..U
....
....
...E

예제 출력 1

6

예제 입력 2

4 2 6
S..U
....
....
...E

예제 출력 2

-1

예제 입력 3

4 3 3
S..U
....
....
...E

예제 출력 3

6

최상단 맨 왼쪽을 (0, 0)이라 하고 최하단 맨 오른쪽을 (3, 3)이라 하자.

안전지대로 이동하는 방법은 (0, 0)에서 출발하여 우산이 있는 (0, 3)에 가고 (3, 3)으로 이동할 수 있다.

이 방식으로 이동한다면 안전지대에 도착했을때 체력이 1이 남는다.

알고리즘 분류

• 백트래킹

풀이

격자의 크기가 최대 500 X 500이 될 수 있기 때문에, 그냥 그래프를 탐색하려고 하면 시간이 초과될 수 있다.

격자에 우산이 최대 10개까지 주어지고, 안전 지대에 도달해야 하며, 체력이 0 이하로 떨어지지 않으면서 안전 지대에 도달해야 하는데, 격자의 칸 개수는 최대 250,000개까지 주어진다. 그런데 체력의 최대치는 10,000까지밖에 주어지지 않는다. 따라서 반드시 우산을 주우면서 가야 안전 지대에 무사히 도착할 수 있다.

안전 지대와 우산이 있는 지점은 최대 11개까지이므로, 이 11개의 지점으로만 이동한다고 가정하면 최대 11!가지의 경우의 수가 존재하므로 1.5초 내에 모든 경우의 수를 다 따질 수 있다.

현재 위치와 우산 혹은 안전 지대가 있는 다음 지점까지 가는 시간과, 도중에 떨어지는 체력, 우산의 내구도 등을 계산하면서, 체력이 0 이하로 떨어지지 않으면서 안전 지대까지 도착할 수 있는 최소의 시간을 구한다.

만약 그런 경우가 존재하지 않는다면 -1을 출력한다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define INF 1e9
#define FASTIO cin.tie(0); cout.tie(0);

using namespace std;
int N, H, D;
pair<int, int> Start, End;
vector<pair<int, int> > Umbrella;
int Answer = INF;

void input() {
    cin >> N >> H >> D;
    for (int i = 0; i < N; i++) {
        string S;
        cin >> S;
        for (int j = 0; j < N; j++) {
            if (S[j] == 'U') {
                Umbrella.push_back(make_pair(i, j));
            }
            else if (S[j] == 'E') {
                Umbrella.push_back(make_pair(i, j));
                End = make_pair(i, j);
            }
            else if (S[j] == 'S') {
                Start = make_pair(i, j);
            }
        }
    }
}

void settings() {
    sort(Umbrella.begin(), Umbrella.end());
    do {
        int NowY = Start.first;
        int NowX = Start.second;
        int NowH = H;
        int NowU = 0;
        int Time = 0;
        for (int i = 0; i < Umbrella.size(); i++) {
            int Y = Umbrella[i].first;
            int X = Umbrella[i].second;
            Time += abs(NowY - Y) + abs(NowX - X);
            int Damage = abs(NowY - Y) + abs(NowX - X) - NowU;
            if (Damage < 0) {
                Damage = 0;
            }
            NowH -= Damage;
            if (NowH < 0) {
                break;
            }
            NowU = D;
            NowY = Y;
            NowX = X;
            if (make_pair(Y, X) == End) {
                if (NowH >= 0) {
                    Answer = min(Answer, Time);
                }
                break;
            }
            else {
                if (NowH < 0) {
                    break;
                }
            }
        }
    } while (next_permutation(Umbrella.begin(), Umbrella.end()));
}

void find_Answer() {
    if (Answer == INF) {
        cout << "-1\n";
    }
    else {
        cout << Answer << "\n";
    }
}

int main() {
    FASTIO
    input();
    settings();
    find_Answer();

    return 0;
}