[백준 22944번] 죽음의 비(C++)

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

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

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

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

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

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

---

 

단순 BFS라고 하기에는 한번 방문한 곳을 다시 지나가는 경우의 수가 있기 때문에 bool visited[][] 배열로는 방문을 처리하기 어렵다.

1. 처음에는 다시 지나가는 케이스를 생각안하고 단순 BFS로 구현했다가 WA

2. 재방문의 경우를 생각하고 우산의 같은 내구도로는 재방문을 할 필요가 없으므로 visited[nx][ny][nd]를 통해 처리를 해주려고 했으나 숫자의 범위가 3차원 배열의 크기가 500*500*5000이 되면서 메모리 초과를 받았다.

3. visited[nx][ny]를 bool배열이 아닌 int타입으로 선언해 안에 가장 큰 체력+내구도 값을 저장해놓았다. 어차피 체력+내구도가 이동할 수 있는 총 거리이고 그보다 작은 경우는 방문할 필요가 없기 때문에 메모리도 줄이면서 문제를 해결할 수 있었다.

 

골드 3이상의 BFS부터는 이렇게 단순 방문이 아닌 중복방문을 어떻게 처리하는지의 문제가 출제되는거 같다.

이전에 풀었던, 아리스 청소합니다!(문제 링크)나 벽 부수고 이동하기(문제 링크) 등을 함께 연습해보면 좋을거 같다.

 

코드는 다음과 같다

#include <iostream>
#include <queue>
using namespace std;

struct State{
  int x,y,h,d,cnt;
};

int n, h, d, start;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
char map[501][501];
int visited[501][501];
queue<State> q;

void trial(){
  while(!q.empty()){
    auto cur = q.front();
    q.pop();
    int x = cur.x;
    int y = cur.y;
    for(int dir = 0; dir < 4; dir++){
      int nx = x + dx[dir];
      int ny = y + dy[dir];
      if(nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
      if(map[nx][ny] == 'E'){
        cout << cur.cnt+1;
        return;
      }
      int nh,nd;
      nd = cur.d;
      nh = cur.h;

      if(map[nx][ny] == 'U')
        nd = d;

      if(nd > 0) nd--;
      else nh--;

      if(nh == 0 || (visited[nx][ny] >= nh+nd)) continue;
      visited[nx][ny] = nh+nd;

      q.push({nx,ny,nh,nd,cur.cnt+1});
    }
  }
  cout << -1;
}

int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> h >> d;
  for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
      cin >> map[i][j];
      if(map[i][j] == 'S') {
        q.push({i,j,h,0,0});
        visited[i][j] = h;
      }
    }
  }
  trial();
  return 0;
}