백준 1103번 게임[C++]

1. 개요

 안녕하세요. "1103번 게임" 문제의 유형은 dfs를 응용한 다이나믹 프로그래밍입니다. dfs는 재귀로 구현하는 방법과 스택을 사용한 반복문 풀이가 존재합니다. 마찬가지로 다이나믹 프로그래밍도 재귀 + 메모이제이션을 사용한 top-down approach와 반복문을 사용한 bottom-up approach가 존재하죠. 둘 다 재귀로 구현이 가능하다는 공통점이 있기도 해서 그런지 이 둘을 합쳐 응용한 문제를 종종 마주치긴 합니다. 원래 저는 bottom-up 풀이 위주의 다이나믹 프로그래밍 풀이를 하다가 dfs와 응용되는 문제를 좀 더 쉽게 접근하기 위해서 top-down 풀이법을 연습했었습니다. 개인적으로 다이나믹 프로그래밍의 구현 난이도가 bottom-up에 비해 top-down이 더 쉽기도 해서 이제는 top-down을 더 애용합니다. 이번 문제는 제가 학부 3학년 때 교내 대회에 등장했었던 문제와 매우 유사했습니다. 그때는 실력이 부족해 풀 수 없었지만 현재는 무난하게 풀 수 있었습니다.

 

2. 문제 풀이

 문제를 읽고 고민하게 된 구현 로직은 두 가지가 있습니다.

 첫 번째로는 사이클을 처리하는 방법입니다. 이전에 방문했던 위치를 재방문했을 때, 사이클이 있다고 처리하는 방법은 다른 경로를 통해 사이클 없이 재방문하는 가능성이 있어 섣불리 구현할 수 없었습니다. 해결 방법은 dfs입니다. dfs는 우선 한 경로로 갈 수 있는 곳까지 이동한 다음 다른 경로를 찾는 원리입니다. 동전을 이동시킨 횟수 배열과 방문 배열을 분리하여 구현하고 재귀를 통해 상태를 저장하는 방식을 사용한다면 현재 이동 중인 경로에 사이클이 있음을 판별할 수 있게 됩니다.

두 번째로는 출발 위치입니다. 문제에서 출발점을 결정하지 않았기 때문에 모든 위치를 한 번씩 탐색을 해야 하나 고민했습니다. 다이나믹 프로그래밍은 이를 해결하기 위한 알고리즘으로 적절합니다. 재귀를 통해 이동하는 위치마다 해당 위치를 출발점이라고 가정하고 로직을 구현하게 되면 이 문제를 쉽게 해결할 수 있습니다. dp 테이블 d[i][j]는 (i, j)에서 출발했을 때 동전의 최대 이동 횟수라고 정의하여 풀이하면 됩니다.

 

3. 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pi; typedef pair<ll, ll> pl;
typedef tuple<int, int, int> ti; typedef tuple<ll, ll, ll> tl; typedef vector<int> vi; typedef vector<ll> vl;
typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<ti> vti; typedef vector<tl> vtl;
typedef vector<string> vs; typedef vector<bool> vb; typedef queue<int> qi; typedef queue<ll> ql;
typedef queue<pi> qpi; typedef queue<pl> qpl; typedef queue<ti> qti; typedef queue<tl> qtl;
#define fastio(x, y) cin.tie((x))->sync_with_stdio((y))
#define X first
#define Y second
#define pb push_back
#define sz(x) (int((x).size()))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const char nl = '\n';

const int dx[4]{1, 0, -1, 0};
const int dy[4]{0, 1, 0, -1};

int n, m;

vs board;
vector<vi> d;
vector<vb> vis;

int dfs(int cx, int cy) {
    if(cx < 0 || cx >= n || cy < 0 || cy >= m || board[cx][cy] == 'H') {
        return 0;
    }

    if(vis[cx][cy]) {
        cout << -1;
        exit(0);
    }

    if(d[cx][cy] != -1) {
        return d[cx][cy];
    }  

    vis[cx][cy] = 1;
    int cur = board[cx][cy] - '0';
    for(int dir = 0; dir < 4; dir++) {
        int nx = cx + dx[dir] * cur;
        int ny = cy + dy[dir] * cur;
        d[cx][cy] = max(d[cx][cy], dfs(nx, ny) + 1);
    }
    vis[cx][cy] = 0;
    return d[cx][cy];
}

int main() {
    fastio(nullptr, false);
    
    cin >> n >> m;

    vs(n).swap(board);
    vector<vi>(n, vi(m, -1)).swap(d);
    vector<vb>(n, vb(m)).swap(vis);

    for(auto &x : board) {
        cin >> x;
    }
    cout << dfs(0, 0);
}

 

4. 제출 결과