사라지는 발판 92345

문제

이하생략

접근 방법

무언가 법칙이 있을 것 같았다.
1. 누가 이기는지 미리 알아야 한다.
2. 그 상황에서 각자 자신에게 유리하게 가야 한다.
이렇게 정리하고 보니 어떻게 해야 할지 몰랐다.
각자 탐색하기에는 상황에 따라 값이 변하기에 안될 것 같았다. 무언가 규칙을 통해 먼저 이기는 사람을 정할 수 있지 않을까 싶어서 생각해봤는데 답이 안 나왔다.
그래서 해설과 다른 사람의 풀이를 봤다.

각자 돌아가며 DFS를 하는 것이다.

코드

#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, int> pos;
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
int dfs(vector<vector<int>> &board, pos p1, pos p2)
{
    if (!board[p1.first][p1.second]) // 내가 밞은 발판이 이미 떠난 발판인지 확인한다.
        return 0;
    int ret = 0;
    for (int i = 0; i < 4; ++i)
    {
        pos next = {p1.first + dy[i], p1.second + dx[i]};
        if (next.first < 0 || next.second < 0 || next.first >= board.size() || next.second >= board[0].size())
            continue;
        if (!board[next.first][next.second])
            continue;
        board[p1.first][p1.second] = 0; // 떠나니까 0이 된다.
        int val = dfs(board, p2, next) + 1;
        board[p1.first][p1.second] = 1;
        if (!(ret % 2) && val % 2)
            ret = val;
        else if (ret % 2 && val % 2)
            ret = min(val, ret);
        else if (!(ret % 2) && !(val % 2))
            ret = max(val, ret);
    }
    return ret;
}

int solution(vector<vector<int>> board, vector<int> aloc, vector<int> bloc)
{
    return dfs(board, {aloc[0], aloc[1]}, {bloc[0], bloc[1]});
}

풀이

매개변수의 위치를 바꾸어 각각 움직이며 DFS를 한다. 만약 마지막에 움직일 수 없다면 0이 반환될 것이다. 패자가 정해졌기에 다음에 움직이는 사람은 승자이고 1번 움직이기에 1의 값을 반환할 것이다. 즉 패자가 반환하는 값은 0, 2, 4...와 같은 짝수이고 승자가 반환하는 값은 1, 3, 5...와 같은 홀수이다.
이외에도 승리, 패배를 같이 반환하여 확인하는 방식도 있다.

(23.01.27 추가)

어제 스터디를 하며 질문을 받았었다. if문으로 최적의 값을 낼 수 있는 이유에 대해서 말이다. 나도 확실히 이해가 안 된 상태에서 대답하기 곤란했고, 해결되지 못한 채로 넘어갔다. 오늘 아침에 버스를 기다리며 생각해본 결과를 적으려 한다.

매 순간 각 위치에 대해서 4개의 경우가 존재한다. 반환된 값은 짝, 홀로 승패를 확인할 수 있다. (또는 bool과 숫자를 같이 반환할 수도 있다)

4패의 결과가 나왔다고 하자. 그렇다면 패에서 반환된 값 중 가장 큰 값을 반환한다. (오래 버텨야 하기 때문이다)
3패 1승의 결과가 나왔다고 하자. 여태까지 쌓인, 또는 앞으로 나올 패의 값이 어떻게 됐든 승의 값으로 갱신하고 다른 값은 무시한다.
어떻게 되든 승기를 이어 나가는 것이 나에게 있어서 필승이기 때문이다.

N패 M승의 결과라면 M승의 결과 중 가장 작은 값을 반환할 것이다. 그것이 나에게 유리하기 때문이다.

나의 승리는 상대방에게 있어서 패배이다.
하지만 상대방에게도 나와 같은 선택지가 있을 수 있다. (4방향이 존재하기 때문이다. 4패 일수도 있고 N패 M승일 수도 있다)
4패이면 마찬가지로 가장 큰 값을 반환한다. N패 M승이면 가장 작은 값을 반환한다.

1승이라도 있다면 그 방향으로 가서 승기를 이어 나가려 할 것이다.

이것을 서로가 갈 수 있는 모든 경우에 관해서 확인해보는 것이다.
가장 말단에 있는 결과가 걸러지고 걸러져서 나에게 왔을 때 패배라는 결과가 확실히 됐다면 가장 질질 끌 수 있는 곳으로 갈 것이고 1승이라도 존재한다면 그 방향으로 갈 것이다. 모든 경우를 탐색했기에 상대 또한 최적의 방향으로 올 것이다. (서로가 조금이라도 비효율적인 길을 갈 일은 없다. 최솟값, 최댓값으로 값을 걸러냈기 때문이다)

그렇기에 반환된 값이 최적의 플레이라고 할 수 있다.