[BOJ] 죽음의 비 22944번 C+

 

문제

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

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

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

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

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

입력

 

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

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

 

출력

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

 

 

접근 방식

 

생각보다 정말 오래걸렸던 문제다....

백트래킹으로 풀어야 겠다는 생각에 무작정 재귀를 사용해서 풀었다

당연히 시간초과가 발생했고...

최단거리 경로 문제일 경우 BFS로 다시 풀어봐야 겠다는 생각이 들어서 큐로 다시 한번 접근방식을 바꿨다

하지만 여전히 정답이 맞지 않았다!!

 

다시 문제를 꼼꼼이 읽어보니

우산, 체력에 따라 최단 경로가 달라질 수 있다는 점을 방문 배열에 함께 처리해야 겠다는 생각이 들었다

 

즉, 방문배열에 현재 우산의 내구도와 체력을 모두 저장하며 이동하였다

그랬더니 다행히 성공 할 수 있었다~^.^

 

추가로 큐를 사용하면서 tuple을 사용해 3개 이상의 값을 저장해본적은 있지만

5개의 값을 저장해본적은 처음이였는데

struct를 사용해 간단하게 저장할 수 있었다

 

 

코드

 

#include<bits/stdc++.h>
using namespace std;

int N, H, D, ans = INT_MAX;
char mat[505][505];
bool visited[505][505][11][11]; // 체력과 우산 상태까지 고려한 방문 배열
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

struct State {
    int x, y, health, umbrella, cnt;
};

queue<State> q;

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> N >> H >> D;

    pair<int, int> st;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> mat[i][j];
            if (mat[i][j] == 'S') {
                st.first = i;
                st.second = j;
            }
        }
    }

    memset(visited, false, sizeof(visited));
    q.push({st.first, st.second, H, 0, 0});
    visited[st.first][st.second][H][0] = true;

    while (!q.empty()) {
        State cur = q.front();
        q.pop();

        if (cur.health <= 0) continue;

        for (int r = 0; r < 4; r++) {
            int nx = cur.x + dx[r];
            int ny = cur.y + dy[r];
            int nu = cur.umbrella;
            int nh = cur.health;
            int nc = cur.cnt + 1;

            if (nx < 0 || ny < 0 || nx >= N || ny >= N || mat[nx][ny] == 'S') continue;

            if (mat[nx][ny] == 'E') {
                ans = min(ans, nc);
                continue;
            }

            if (mat[nx][ny] == 'U') nu = D-1;

            if (mat[nx][ny] == '.') {
                if (nu > 0) nu--;
                else if (nh > 0) nh--;
            }

            if (!visited[nx][ny][nh][nu]) {
                visited[nx][ny][nh][nu] = true;
                q.push({nx, ny, nh, nu, nc});
            }
        }
    }

    if (ans == INT_MAX) cout << -1;
    else cout << ans;

    return 0;
}