[COCI] 백준 3055 - 탈출

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

3055번: 탈출

 

문제를 잘 이해해야 한다. 이동과 범람이 동시에 일어난다고 되어있다.

 

주어진 조건대로 이동을 잘 시뮬레이션하기 위해서는 이동을 먼저 한 다음 범람을 일으켜야 한다.

 

이 순서로 BFS를 진행해서 이동한 위치에 범람이 될 예정인지 아닌지는 신경쓰지 않고 큐에 넣는다.

 

그다음 범람을 수행한다.

 

그렇게 이동이 1회 끝난 뒤 다음 큐에서 꺼낼 때 범람된 상태면 해당 노드를 탈락시키고 다음 노드를 꺼내서 확인하면 된다.

 

바위는 서로 통과하거나 범람될 수 없고 D 좌표는 범람되지 않는다는 것에 유의하여 BFS를 수행하면 정답을 받을 수 있다.

 

자세한 구현은 밑에 코드를 참조한다.

 

전체 코드

#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

using namespace std;
using pii = pair<int, int>;

int r, c;
string forest[50];
bool visited[50][50];
bool water[50][50];
queue<pii> flood;
int finr, finc;
bool fin;

void solve()
{
  cin >> r >> c;
  queue<vector<int>> q;
  for (int i = 0; i < r; ++i)
  {
    cin >> forest[i];
  }

  for (int i = 0; i < r; ++i)
  {
    for (int j = 0; j < c; ++j)
    {
      if (forest[i][j] == 'D')
      {
        finr = i, finc = j;
      }

      if (forest[i][j] == 'X')
      {
        visited[i][j] = water[i][j] = 1;
      }

      if (forest[i][j] == '*')
      {
        flood.push({i, j});
        visited[i][j] = water[i][j] = 1;
      }

      if (forest[i][j] == 'S')
      {
        q.push({i, j, 0});
      }
    }
  }

  int turn = 250;
  int ans = -1;

  while (turn--)
  {
    if (fin) break;
    queue<vector<int>> nxtq;

    while (q.size())
    {
      auto cur = q.front();
      q.pop();

      if (visited[cur[0]][cur[1]] || water[cur[0]][cur[1]]) continue;

      visited[cur[0]][cur[1]] = true;

      for (int i = 0; i < 4; ++i)
      {
        int nr = cur[0] + ("2213"[i] - '2');
        int nc = cur[1] + ("1322"[i] - '2');

        if (nr < 0 || nc < 0 || nr >= r || nc >= c || visited[nr][nc] || water[nr][nc])
          continue;
        
        if (nr == finr && nc == finc)
        {
          fin = true;
          ans = cur[2] + 1;
          break;
        }
        
        nxtq.push({nr, nc, cur[2] + 1});
      }
    }

    q = nxtq;
  
    queue<pii> next_flood;

    while (flood.size())
    {
      auto cur = flood.front();
      flood.pop();

      for (int i = 0; i < 4; ++i)
      {
        int nr = cur.first + ("2213"[i] - '2');
        int nc = cur.second + ("1322"[i] - '2');

        if (nr < 0 || nc < 0 || nr >= r || nc >= c || water[nr][nc] || (finr == nr && finc == nc))
          continue;
        
        water[nr][nc] = 1;
        next_flood.push({nr, nc});
      }
    }

    flood = next_flood;
  }

  if (ans != -1) cout << ans;
  else cout << "KAKTUS";
}

int main()
{
  cin.tie(nullptr);
  ios::sync_with_stdio(false);

  solve();
}