백준 30689 - 미로 보수

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

 

이 문제는 단순히 "사이클로 들어가는" 노드 중에서 최소 비용을 가진 노드만 택하면 틀렸습니다를 받는다.

 

문제에 주어진 그래프는 함수형 그래프인데, 이런 경우가 흔히 발생할 수 있기 때문이다.

 

 

단순한 사이클 찾기를 통해 그룹을 묶는다면, 그림과 같이 문제 조건에서 고려할 수 있는 유의미한 사이클 외에 1, 2번 노드에서 비용을 고르는 경우가 생길 수 있다.

 

따라서 문제를 해결하기 위해서는 유효한 사이클만 검출하도록 할 필요가 있다.

 

 

그러기 위해서는 그래프의 모든 노드에서 엣지를 따라가되, 이미 방문했지만 종결되지는 않은 노드로 다시 방문하게 되는 순간, 해당 노드부터 시작하는 "유의미한 사이클"을 추적하여 최소 비용을 찾도록 하면 된다.

"유의미한 사이클"에 속한 노드 중 최소 비용을 가진 노드를 골라 총비용에 더해준 뒤, 사이클을 종결처리 해주면서 그래프를 탐색하면 단순히 사이클에 진입만 하는 노드가 계산되는 일을 막아 올바른 답을 구할 수 있다.

 

정답 코드 - CPP

// #pragma GCC target("fma,avx,avx2,bmi,bmi2,lzcnt,popcnt")
#pragma GCC optimize("O3,unroll-loops")
 
#include "bits/stdc++.h"
#include "ext/pb_ds/assoc_container.hpp"
 
using namespace std;
using namespace __gnu_pbds;
 
using ll = int_fast64_t;
using pii = pair<int, int>;
// using oset = tree<int, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>;
 
int n, m;
string board[2000];
int fee[4000002];
int discovered[4000002];
int node_next[4000002];
int ans;
 
void solve()
{
  memset(discovered, -1, sizeof discovered);
  cin >> n >> m;
  for (int i = 0; i < n; i++)
  {
    cin >> board[i];
  }
 
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < m; j++)
    {
      cin >> fee[i * m + j];
    }
  }
 
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < m; j++)
    {
      int dr = 0, dc = 0;
      if (board[i][j] == 'U') dr = -1;
      if (board[i][j] == 'D') dr = 1;
      if (board[i][j] == 'R') dc = 1;
      if (board[i][j] == 'L') dc = -1;
 
      int cr = i + dr;
      int cc = j + dc;
      
      int go = i * m + j;
      int to = cr * m + cc;
 
      if (cr < 0 or cc < 0 or cr >= n or cc >= m) 
      {
        node_next[go] = -1;
        continue;
      }
 
      node_next[go] = to;
    }
  }
 
  for (int i = 0; i < n * m; i++)
  {
    if (discovered[i] == 2) continue;
    vector<int> footprint;
 
    int here = i;
    while (here != -1 and discovered[here] == -1)
    {
      discovered[here] = 1;
      footprint.push_back(here);
      here = node_next[here];
    }
 
    int idx = 0;
    while (footprint[idx] != here and idx < footprint.size())
    {
      discovered[footprint[idx]] = 2;
      ++idx;
    }
 
    if (idx >= footprint.size()) continue;
    int val = 1e9;
 
    while (idx < footprint.size())
    {
      val = min(val, fee[footprint[idx]]);
      discovered[footprint[idx]] = 2;
      ++idx;
    }
 
    ans += val;
  }
 
  cout << ans;
}
 
int main()
{
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
 
  solve();
}