이번 문제는 프로그래머스 레벨 3 문제 사라지는 발판 문제이다.
2022 카카오 공채 문제여서 그런지 굉장히 난이도가 높다.
먼저 문제를 차근차근 읽어보자.
최대 5 x 5의 게임 판이 주어지고 A와 B가 게임을 진행한다.
항상 플레이어 A가 먼저 말을 움직이며 게임을 시작하게 된다.
이 때 게임 판에서 발판이 없는 위치로는 움직일 수 없다.
플레이어가 지나간 자리는 반드시 발판이 없어지게 된다.
또한, 두 플레이어는 같은 발판 위에 위치할 수 있다.
이 때 발판의 상태에 따라 이길 수 밖에 없는 플레이어가 정해진다.
이는 실수를 하지 않았을 때 이길 수 밖에 없음을 의미한다.
이길 수 밖에 없는 플레이어는 최대한 빨리 게임을 이기려 하고,
질 수 밖에 없는 플레이어는 최대한 늦게 지려고 한다.
서로에게 최적의 결과를 도출하는 프로그램을 만들어라!
문제 분석
아무래도 게임 이론에 대한 문제 같은데 굉장히 어렵다..
서로 둘 수 있는 모든 수를 둬봐야 할 것 같기 때문에,
가장 먼저 든 생각은 백트래킹으로 문제를 푸는 것이다.
백트래킹을 통해서 두 플레이어가 둘 수 있는 모든 경우를 둔다.
백트래킹
단순하게 백트래킹을 이용해서 두 플레이어의 모든 경우를 구현하려 했다.
하지만 과연 어떤 상태가 최적의 수인지를 알 수가 없었다.
둘 중 반드시 이길 사람을 어떻게 미리 알고 구현할 것인가?
단순히 턴을 최대로 쓰는 방향이 답이 되는 것은 아니다.
게임 이론
결국 고민 끝에 다른 사람의 풀이를 참고하게 되었다.
게임 이론의 Minimax Tree를 이용하여 푸는 문제라고 한다.
게임 이론에 있어서, 최적의 수를 둔다는 것은 아래와 같은 의미이다.
두 플레이어 모두가 최적의 수를 두므로, 승패는 중요하지 않다.
두 플레이어가 모두 최적의 수를 두었을 때 사용되는 턴을 말하는 것이다.
사실 위의 말만 보았을 때 의미를 파악하기가 쉽지 않다.
단순히 생각해보자. 이길 수 있다의 의미는 무엇일까?
어떤 수를 두어나갔을 때, 한번이라도 이기면 이길 수 있는 것이다.
그럼 질 수 밖에 없다는 어떤 의미를 가질까?
어떤 수를 두어나갔을 때, 한번도 이기지 못하면 질 수 밖에 없다.
이길 수 있는 플레이어는 턴을 최대한 빨리 끝내려고 한다.
즉, 최소의 턴을 반환하게 되는 것이다.
질 수밖에 없는 플레이어는 턴을 최대한 지연시키려고 한다.
즉, 최대의 턴을 반환하도록 해야 하는 것이다.
이것이 바로 Minimax Tree 알고리즘의 핵심 논리이다.
보통은 동적계획법을 통해서 게임 이론을 풀어나간다고 한다.
하지만 이번 문제는 게임 판이 크지가 않아, 완전 탐색이 가능하다.
완전 탐색을 진행하며 몇 번째 턴까지 진행 가능한지 계산하도록 한다.
구현
첫번째로 구현해야 할 것은 당연히 재귀함수의 구조이다.
나는 처음에 재귀함수로 두 플레이어의 위치를 각각 동시에 바꿀 생각이었다.
즉 재귀 한 번에 턴을 두 번 사용하며 플레이어를 옮기려했다.
하지만 이는 매우 복잡한 분기를 타게 된다.
backtrack(curr_x, curr_y, cont_x, cont_y)와 같이 구조를 작성하자.
backtrack(cont_x, cont_y, curr_x, curr_y)로 값을 넘겨주게 된다면?
결국 현재 플레이어는 상대방이 되고, 상대 플레이어는 현재 플레이어가 된다.
이런 구조로 코드를 작성하게 되면 훨씬 깔끔해진다.
또한, 턴을 계산하는 방식 또한 더 깔끔하게 작성할 수 있다.
원래는 turn이라는 변수를 만들어 최소, 최대 턴을 저장하려 했다.
하지만 return type 자체를 int형으로 만들어 턴을 반환하면?
따로 변수를 만들고 초기화 할 필요 없이 그 때 그 때 턴을 세어줄 수가 있다.
이제 문제는 이길 수 있는 경우와 질 수 밖에 없는 경우를 검사하는 것!
턴을 계속 계산하며 나아간다고 가정했을 때, 끝났을 때의 턴을 보면 된다.
- 만약 끝났을 때의 턴이 짝수라면?
- 이는 A가 패배했음을 의미한다.
- 만약 끝났을 때의 턴이 홀수라면?
- 이는 B가 패배했음, 즉 A의 승리를 의미한다.
즉 우리는 끝났을 당시의 턴을 보고 경우를 분류해야 한다.
우리는 턴을 저장해서 반환할 변수인 result와
현재의 턴에 대해 이겼는 지 졌는 지를 판단할 curr_turn을 사용한다.
아래의 그림을 보면 이해하기가 더 쉬울 것이다.
그림을 보면 curr_turn은 n수 뒤의 상태를 의미한다.
그래서 현재 내가 플레이어 A라고 했을 때, 해당 경우 끝에 B가 패배했다면?
curr_turn이 홀수일 때마다 A의 차례가 되는 것이고, 이긴게 되는 것이다.
result 값은 내려갔던 4가지의 경우들에 대해서 검사하는 것이다.
n수 뒤의 결과에 따라 해당 n을 result에 저장하는 것인데,
다른 경우들에서 이미 이겼다면 이길 수 있는 경우이므로 최소를 저장한다.
다른 경우들에서 이긴 적이 한번도 없는데, 즉 result가 짝수일 때
curr_turn도 짝수라면 질 수 밖에 없는 경우이므로, 최대를 저장한다.
마지막으로 이긴 적이 한번도 없는데, curr_turn이 홀수라면?
이는 한번이라도 이긴 것이므로 이길 수 있는 경우에 해당, 갱신한다.
최종적으로 아래와 같이 구현되었다.
int backtrack(int curr_x, int curr_y, int con_x, int con_y, vector<vector<int>> &board) {
if (visit[curr_x][curr_y])
return 0;
// 현재 진행하는 플레이어가 밟은 발판이 사라졌으면 중단
int result = 0;
for (int i = 0; i < 4; i++) {
int nx = curr_x + dx[i];
int ny = curr_y + dy[i];
// 다음 방향 검사
if (nx < 0 || nx >= board.size() || ny < 0 || ny >= board[0].size())
continue;
if (visit[nx][ny] || !board[nx][ny])
continue; // 이미 없어진 발판으로는 갈 수 없음
visit[curr_x][curr_y] = true;
// 플레이어가 지나간 곳! 발판 없애기
int curr_turn = backtrack(con_x, con_y, nx, ny, board) + 1;
// 상대편의 위치를 다음 매개변수로 넘긴다.
// 이는 상대편의 턴으로 넘어갔음을 의미, 완료시 (턴 + 1)을 반환한다
visit[curr_x][curr_y] = false;
cout << result << " " << curr_turn << '\n';
// 이 아랫부분이 이번 풀이의 핵심이다.
// Case 1. 저장된 턴은 패배, 새로 계산된 턴은 승리인 경우
if (result % 2 == 0 && curr_turn % 2 == 1)
result = curr_turn; // 이긴 경우로 바로 갱신해야 함
// Case 2. 저장된 턴도 패배, 새로 계산된 턴도 패배인 경우
else if (result % 2 == 0 && curr_turn % 2 == 0)
result = max(result, curr_turn); // 최대한 늦게 져야 함
// Case 3. 저장된 턴도 승리, 새로 계산된 턴도 승리인 경우
else if (result % 2 == 1 && curr_turn % 2 == 1)
result = min(result, curr_turn); // 최대한 빨리 이겨야 함
}
return result;
}만약 코딩 테스트에 이런 문제가 나왔다면, 손도 못대고 틀렸을 것이다.
이해하는 데에 꽤 많은 시간을 소모했다.
게임 이론에 대해서 조금 더 공부를 할 필요가 있을 것 같다.