백준 1103 - 게임

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

 

이 포스트에서는 다소 무식한 방법을 사용한다.

 

일단 동적 계획법을 수행할 건데 테이블에서 상태는 "해당 위치를 갈 수 있는가?"로 정의하며 각 이동을 계산해 현재 테이블에서 다음 테이블로 바꾸는 방법을 사용할 것이다.

 

그러면 각 위치에서 상태가 1일 때(처음에는 (0, 0)만 1이다.) 주어진 조건에 따라갈 수 있는 좌표를 모두 1로 갱신하면 될 것이다. 물론 기존 테이블에다 갱신하는 게 아니라 다음에 쓸 테이블에다 해야 한다.

 

그러면 위치를 갱신하는 dp를 돌린다는 건 알겠는데 몇 번 하는가? 가 중요할 것이다.

 

어떤 특정한 횟수를 넘어서도 계속 이동할 수 있다면 게임을 무한으로 할 수 있다는 의미가 된다.

 

그러면 그 임계값을 정해야 하는데 특별한 답은 없다. 적당히 잘 정해야 한다.

 

본인은 n * m * 2 정도로 해봤는데 틀리고 n * m * 3부터 정답이 떴다.

 

아무튼 이 임계값을 잘 설정해서 dp로 시뮬레이션을 하면 최대 횟수 혹은 무한히 게임을 하는지 구할 수 있다.

 

전체 코드

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
#include "bits/stdc++.h"
#include "ext/rope"
 
using namespace std;
using namespace __gnu_cxx;
 
using ll = long long;
using pii = pair<int, int>;
 
int r, c;
string grid[50];
vector<vector<int>> dp;
 
void solve()
{
  cin >> r >> c;
  for (int i = 0; i < r; i++)
  {
    dp.push_back(vector<int>(c, 0));
    cin >> grid[i];
  }
 
  dp[0][0] = 1;
  for (int i = 1; i <= r * c * 3; i++)
  {
    vector<vector<int>> ndp = vector<vector<int>>(r, vector<int>(c, 0));
    bool pulse = false;
 
    for (int j = 0; j < r; j++)
    {
      for (int k = 0; k < c; k++)
      {
        if (!dp[j][k]) continue;
 
        int num = grid[j][k];
        if (num == 'H') continue;
        num -= '0';
 
        for (int s = 0; s < 4; s++)
        {
          int nr = j + ("1102"[s] - '1') * num;
          int nc = k + ("0211"[s] - '1') * num;
 
          if (nr < 0 or nc < 0 or nr >= r or nc >= c or grid[nr][nc] == 'H') continue;
          pulse = true;
          ndp[nr][nc] = 1;
        }
      }
    }
 
    if (!pulse)
    {
      cout << i;
      return;
    }
    dp = ndp;
  }
 
  cout << -1;
}
 
int main()
{
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
 
  solve();
}

제출 기록

보너스

이 풀이에서 쓴 방법을 쓸 수 있는 문제가 또 있다.

 

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

14962번: Vacation Plans

 

얘는 최대 3명이 별개의 그래프에서 간선 이동 비용과 정점에 머무르는 비용이 있고 주어진 도착지까지 가는 최소 비용을 찾는 문제인데 얘도 대충 x번 움직여보는 방법으로 정답을 구할 수 있다.

 

그 x번이 몇일지는 여러분이 직접 유추하도록 하자.