[DP] 백준 28218 격자 게임

 

 어떤 알고리즘으로 문제를 풀어야 할까?  문제의 크기는 300 * 300에, 말의 위치가 다시 원위치로 돌아가는 방법이 없다. 문제를 하위 문제로 나누어 풀어도 문제가 없다는 이야기. 즉, dynamic programming이 가능한 문제라는 뜻이다. 점화식을 어떻게 수립해야 할까? 

$$dp[x][y][turn]$$

(x, y)의 위치에서 현재 turn(한국 or 정올)의 차례일 때 이기는 사람의 번호로 점화식을 정의할 수 있다. 그렇다면, 최선을 다한다는 것은 어떻게 표현할까? 현재 첫번째 한국이가 이길 때를 0으로 표시하고, 두번째 정올이가 이길 때를 1로 설정한다. 그리고, 첫번째 한국이의 turn일 때는 정올이가 이긴다고(=1) 초기값을 설정하고 가능한 케이스에서 최소값(=0, 한국이가 이기는 케이스가 있는지)를 구해본다. 반대로, 두번째 정올이의 turn일 때는 한국이가 이긴다고(=0) 초기값을 설정하고 가능한 케이스에서 최대값(=1, 정올이가 이기는 케이스가 있는지)를 구해주면 된다. 말로는 복잡하다. 코드로 살펴보자.

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;
#define fastio cin.tie(0)->sync_with_stdio(0)

using ll = long long;
using matrix = vector<vector<ll>>;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using pii = pair<int, int>;
using vpii = vector<pii>;
using vb = vector<bool>;

// BJ_28218 F20, S37
// dp[x][y]로 생각하고 전개하다가, turn에 따라 대각선과 평행 이동 충돌 발생 확이후
// dp[x][y][turn]으로 변경, 모든 시작 위치에 공유 

// 풀이 1. turn을 고려해서 각자의 turn에서 최선을 다하는 경우를 dp formulating
int n, m, k, q;
vector<string> tmap;
vvvi dp;

int go(int x, int y, int turn) {
    if(x==n-1 && y ==m-1) {
        if(turn) return 0;
        return 1;
    }
    if(dp[x][y][turn] != -1) return dp[x][y][turn];
    int &ans = dp[x][y][turn];
    if(turn) {
        ans = 0; // 2번째 turn에서는 1번째가 이긴다고 세팅하고 max로 최선을 다함
        if(x+1 < n && tmap[x+1][y] != '#') ans = max(ans, go(x+1, y, (turn+1)%2));
        if(y+1 < m && tmap[x][y+1] != '#') ans = max(ans, go(x, y+1, (turn+1)%2));
        for(int i=1; i<=k; ++i) {
            if(x+i < n && y+i < m && tmap[x+i][y+i] != '#') ans = max(ans, go(x+i, y+i, (turn+1)%2));
        }
    }
    else {
        ans = 1; // 1번째 turn에서는 2번째가 이긴다고 세팅하고 min로 최선을 다함
        if(x+1 < n && tmap[x+1][y] != '#') ans = min(ans, go(x+1, y, (turn+1)%2));
        if(y+1 < m && tmap[x][y+1] != '#') ans = min(ans, go(x, y+1, (turn+1)%2));
        for(int i=1; i<=k; ++i) {
            if(x+i < n && y+i < m && tmap[x+i][y+i] != '#') ans = min(ans, go(x+i, y+i, (turn+1)%2));
        }
    }
    return ans;
}

void solve() {
    cin >> n >> m >>k;
    tmap = vector<string>(n);
    // (x, y, turn)의 위치에 있을 때 누가 이기는지 저장하는 배열
    // turn을 추가함으로써 계산과정에서 공유 가능 
    dp = vvvi(n, vvi(m, vi(2, -1)));
    for(int i=0; i<n; ++i) cin >> tmap[i];
    cin >> q;
    for(int i=0; i<q;++i) {
        int x, y;
        cin >> x >> y;
        --x, --y;
        int ans = go(x, y, 0);
        if(ans) cout << "Second\n";
        else cout << "First\n";
    }
}

int main() {
    fastio;
    solve();
    return 0;
}

 한가지 주의해야 할 점은 300개의 query에서 일일이 처음부터 구하면 시간초과를 받게 된다. 시작위치에 따라서 값을 구하되 dp배열은 계산한 배열을 공유해도 전혀 문제가 없다. 

 그런데, 좀더 간단하게 풀수 있는 방법이 존재할까? 위의 점화식에서 turn을 제거해 보자. 

$$dp[x][y]$$

 (x, y)를 시작위치로 할 때 먼저 시작하는 사람이 이기는지 여부 라고 정의한다면 문제를 풀 수 있을까? 첫번째가 이기지 못한다는 것은 두번째가 이긴다는 것이고, 두번째가 이기지 못하면 첫번째가 이기는 binary 문제다. 그렇다면 첫번째가 아무리 해도 이기지 못하는 경우는 두번째가 이긴다고 생각해도 될까? 그렇다. 첫번째는 자신이 무조건 이길 수 있는 방법을 향해 처음부터 움직이기 때문에 어떻게 해도 첫번째가 이기지 못하는 경우에만 두번째가 우승할 수 있다. 훨씬 간결하게 문제를 풀 수 있다. 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;
#define fastio cin.tie(0)->sync_with_stdio(0)

using ll = long long;
using matrix = vector<vector<ll>>;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using pii = pair<int, int>;
using vpii = vector<pii>;
using vb = vector<bool>;

// 풀이 2. 첫번째 순서가 이기 못하면 무조건 두번째 순서가 이기는 경우다.
int n, m, k, q;
vector<string> tmap;
vvi dp;

int go(int x, int y) {
    if(dp[x][y] != -1) return dp[x][y];
    int &ans = dp[x][y];
    // 한가지 경우라도 해당되면 더 볼 필요없음
    if(x+1 < n && tmap[x+1][y] != '#' && !go(x+1, y)) return ans = 1;
    if(y+1 < m && tmap[x][y+1] != '#' && !go(x, y+1)) return ans = 1;
    for(int i=1; i<=k; ++i) {
        if(x+i < n && y+i < m && tmap[x+i][y+i] != '#' && !go(x+i, y+i)) return ans=1;
    }
    return 0; // 아무리 해도 첫번 째가 이길 수 없다면 두번째가 이기는 것이다. 
}

void solve() {
    cin >> n >> m >>k;
    tmap = vector<string>(n);
    // (x, y)를 시작위치로 할 때 먼저 시작하는 사람이 이기는지 여부
    dp = vvi(n, vi(m, -1));
    dp[n-1][m-1] = 0; // (n-1, m-1)에서 시작하면 두번 째가 이긴다는 이야기
    for(int i=0; i<n; ++i) cin >> tmap[i];
    cin >> q;
    for(int i=0; i<q;++i) {
        int x, y;
        cin >> x >> y;
        --x, --y;
        int ans = go(x, y);
        if(ans) cout << "First\n";
        else cout << "Second\n";
    }
}

int main() {
    fastio;
    solve();
    return 0;
}