[ICPC] 백준 3860 - 할로윈 묘지

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

힌트

이 문제는 그래프를 제대로 모델링하지 않으면 틀리는 문제다. 다음 요소를 점검해보자.

 

1. 도착지에서 이동을 불허하는지?

 

2. 도착 여부보다 음의 사이클 검출 여부가 우선이다.

 

3. 귀신 구멍에 대한 처리를 제대로 한 게 맞는지?

 

다음 TC에 대해 답이 Never가 나와야 한다. 확인해보자.

3 3
2
2 1
1 2
1
1 0 1 0 -1
0 0

솔루션

겉으로 보기엔 벨만포드 알고리즘을 적용하기만 하면 되는 문제로 보인다.

 

다만 주어진 규칙에 따라 가중치 그래프를 제대로 만들지 않으면 틀린 답을 얻게 된다.

 

규칙을 다시 정리하면

 

도착하는 즉시 빠져나와야 하고

 

귀신 구멍에 들어가면 지정한 위치로 이동하며

 

묘비로는 갈 수 없다.

 

주어진 상황을 올바르게 모델링하기 위해서는 각 격자를 인접 리스트로 변환하는 것을 추천한다.

 

격자에서 상하좌우로 이동하는 방법을 채택하게 되면 도착지에 도착하거나 귀신 구멍에 들어가는 경우에 대해 적절한 구현을 찾기 힘들 수 있다.

 

그래프를 "잘" 모델링 하게되면 벨만포드 알고리즘을 수행해서 최단경로, 음의 사이클 여부, 도착 여부를 확인하도록 하자.

 

참고로 문제에서 영원히 과거로 가는 경우(음의 사이클 발견)가 있으면 무조건 Never를 출력하라고 했으므로 참고하면서 구현을 하면 정답을 받을 수 있다.

 

전체 코드 - SPFA

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

#include <bits/stdc++.h>

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

#define NODE_MAX 31
vector<vector<int>> graph[31][31];
bool iswarp[31][31];
bool stone[31][31];
ll dist[NODE_MAX][NODE_MAX];
int node_cnt[NODE_MAX][NODE_MAX];
bool inq[NODE_MAX][NODE_MAX];

int r, c, g;
int mr[4] {1, 0, 0, -1};
int mc[4] {0, -1, 1, 0};

bool spfa(int limit)
{
  fill(&dist[0][0], &dist[0][0] + 31 * 31, 1e18);
  memset(inq, 0, sizeof inq);
  memset(node_cnt, 0, sizeof node_cnt);
  dist[0][0] = 0;
  inq[0][0] = 1;
  ++node_cnt[0][0];
  queue<pii> q;
  q.push({0, 0});

  while (q.size())
  {
    auto cur = q.front();
    q.pop();
    int u = cur.first, v = cur.second;
    inq[u][v] = false;

    for (int i = 0; i < graph[u][v].size(); ++i)
    {
      auto &tmp = graph[u][v][i];
      int nu = tmp[0], nv = tmp[1], w = tmp[2];
      if (dist[u][v] + w < dist[nu][nv])
      {
        dist[nu][nv] = dist[u][v] + w;
        if (!inq[nu][nv])
        {
          if (++node_cnt[nu][nv] >= limit) return false;
          q.push({nu, nv});
          inq[nu][nv] = true;
        }
      }
    }
  }

  return true;
}

void solve()
{
  cin >> c >> r;

  while (r && c)
  {
    for (int i = 0; i < r; ++i)
      for (int j = 0; j < c; ++j)
        graph[i][j].clear();
    memset(stone, 0, sizeof stone);
    memset(iswarp, 0, sizeof iswarp);
    cin >> g;

    for (int i = 0; i < g; ++i)
    {
      int h, w;
      cin >> w >> h;
      stone[h][w] = true;
    }

    int e;
    cin >> e;

    for (int i = 0; i < e; ++i)
    {
      int n, m, h, w, fee;
      cin >> m >> n >> w >> h >> fee;
      iswarp[n][m] = true;
      graph[n][m].push_back({h, w, fee});
    }

    for (int i = 0; i < r; ++i)
    {
      for (int j = 0; j < c; ++j)
      {
        if (stone[i][j] || iswarp[i][j] || (i == r - 1 && j == c - 1))
          continue;
        
        for (int k = 0; k < 4; ++k)
        {
          int nr = i + mr[k], nc = j + mc[k];
          if (nc < 0 || nr < 0 || nr >= r || nc >= c || stone[nr][nc])
            continue;
          
          graph[i][j].push_back({nr, nc, 1});
        }
      }
    }

    bool flag = spfa(r * c);
    if (!flag)
      cout << "Never\n";
    else if (dist[r - 1][c - 1] == 1e18)
      cout << "Impossible\n";
    else
      cout << dist[r - 1][c - 1] << '\n';

    cin >> c >> r;
  }
}

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

  solve();
}

제출 기록

플래티넘을 받을 가치가 있는 문제다.