1. 문제 설명
폴가이즈 게임의 바닥 떨어져유를 생각하면 된다.
한 가지 다른 점은 하나의 발판에서 다른 발판으로 이동해야지만, 기존의 밟고 있던 발판이 사라진다는 것이다.
경기 규칙은 다음과 같다.
- 5*5 이하의 보드가 주어진다. 해당 보드는 밟을 수 있는 발판(1), 발판이 없는 허공(0)으로 이루어져 있다.
- 무조건 2명의 플레이어만 존재한다. 플레이어 A와 플레이어 B가 있다.
각 플레이어는 각자의 turn에 상하좌우 사방으로 한 칸씩만 이동할 수 있다.
플레이어가 이동한 경우, 기존에 밟고 있던 발판은 사라지고 허공(0)으로 변한다. - 승리 조건은 다음과 같다.
한 player가 허공으로 둘러쌓이거나, 딛고 있던 발판이 사라지면, 반대편 player가 이긴다.
(만약 플레이어 A,B가 같은 발판을 밟고 있다가 A가 다른 쪽으로 이동하면, 같이 밟고 있던 발판이 사라져 B는 떨어지고 탈락한다.)
또 하나 중요한 점은 모든 플레이어가 이기기 위해 최선을 다한다.라는 것이다. 최선을 다한다는 다음과 같다.
만약 특정 플레이어가 이길 수 있다면, 이기는 가장 빠른 길(두 플레이어 움직임 최소화)을 택한다.
만약 특정 플레이어가 지는 경우의 수 밖에 없다면 최대한 시간을 끄는 길(두 플레이어 움직임 최대화)을 택한다.
다음과 같이 양 플레이어가 최선의 플레이를 했을 때 두 캐릭터가 움직인 수를 구하여라
2. 푸는 방식
KEY WORD: miniMax Algorithm, DFS
해당 문제는 풀이를 봤다. 풀이를 보게 한 가장 큰 이유는, 각자 최선의 플레이를 했다.를 '어떻게 구현해야할지 감이 잡히지 않아서' 이다.
A,B 특정 플레이어 중 한 명은 자신에게 이길 경우의 수가 있다는 것을 게임 시작부터 알아서, 그 수대로 게임을 진행해야 할 것이고, 반대편 플레이어는 특정 시점부터 자신에게 지는 경우의 수밖에 없다는 것을 알고, 최대한 시간을 끌어야 한다. 이걸 어떻게 나타내야 하는지 정말 막막했다. 이 답답함은 minMax algorithm을 공부하면서 많이 해소되었다. 혹시 minMax algorithm을 이미 안다면 (1)번은 건너 뛰고 다음 부터 봐라
(1) MiniMax algorithm
해당 알고리즘은 두 명의 플레이어가 진행하고 승패가 명확히 갈리는 게임(Zero-sum Game)에서 활용할 수 있는, 움직임 최적화 알고리즘이다.
움직임 최적화란 상대방이 행한 플레이의 영향력을 최소화하고, 내 움직임의 영향력을 극대화하여 승리 확률을 높이는 것을 의미한다. 이세돌과 바둑을 두는 알파고를 생각하면 이해가 편하겠다. (물론 알파고는 MCTS라는 다른 알고리즘을 활용했다...)
Zero-sum 게임을 예로 들어 설명하겠다. Zero-sum 게임에는 체스, 바둑 등 여러가지가 있지만, 그 중에서 경우의 수가 작고 쉬운 tic-tac-toe라는 게임을 예로 들겠다. 틱택토는 둘이 하는 빙고 같은 게임이다. 이를 모르시는 분들을 위해, 게임 설명 링크를 남기겠다.
알고리즘의 순서는 다음과 같다.
- 나를 A, 상대방을 B라고 두겠다.
- DFS로 모든 경우의 수를 따져볼 것이다. 하지만 DFS와 다른 점은 재귀를
DEPTH마다 A와 입장과 B의 입장을 번갈아 취한다는 것이다.
(예를 들어 틱택토 플레이를 재귀로 나타낸다면,
depth1 : A가 동그라미를 한 위치에 그린다.
depth2: B가 엑스표를 한 위치에 그린다.) 이 재귀를 게임이 결판날 때까지 반복한다. - 현재 내가 A이므로, A 입장의 재귀에서는 DFS branch(경우의 수) 중 A가 승리할 최선의 수를 골라야 한다.
- B의 입장 재귀에서는 DFS branch 중 A가 패배할 확률이 제일 높은 수를 골라야 한다.
- 이런 식으로 loop back을 하면, DFS의 root에서는
B가 최선의 플레이를 했을 때 A가 고를 수 있는 현재 최선의 수가 무엇인지 나온다.
글만으로 어려우니 그림으로 예를 들어 보겠다.
먼저 다음과 같이 규칙을 세워보자.
- A가 X를 그리고, B가 O를 그린다.
- 최종적으로 A가 이기는 경우의 수면 1을, 비기면 0을 지면 -1을 반환한다.
경우의 수가 너무 많아서, 게임을 어느 정도 진행한 상황으로 가정한다. 총 3 turn이 남았고, A-> B -> A 로 이루어진다.
- 일단 모든 경우에 DFS가 이루어져서,
DEPTH 3에서 나올 수 있는 모든 결과가 나와있다. DEPTH 3에서는 나올 수 있는 경우의 수가 모두 한 가지라서, 따질 필요 없이 결과값을 반환하면 된다.DEPTH 2는 B의 Turn이다. B가 동그라미를 그린 위치에 따라 비기거나 이기거나 결정됨을 알 수 있다.
이때, B가 A를 이길 경우의 수는 없으므로, 최선의 플레이를 위해, A랑 비기는 경우의 수를 이전 DEPTH로 반환한다.
(세번째 branch는 B가 뭘하든 진다. 따라서 그대로 1을 반환한다.)DEPTH 1은 A의 turn이다. A가 X표를 그리는 위치에 따라 비기거나 이긴다. A에게 최선의 수를 선택해야 하므로, 3번째 branch를 고른다. A가 세번째 branch를 고르는 순간 B는 확정적으로 진다.
이제 이것을 문제에 적용해보자.
(2) 문제 접근 방식
어 근데? minMax는 나(A)와 상대방(B)이 정해져 있고, 내가 이기는 최선의 수를 구하는 알고리즘이라면, 해당 문제에서는 A와 B 중 둘 중 누가 이겨도 되고, 단지 최적의 플레이를 했을 때 turn 횟수를 세면 되지 않나요?
맞다 그래서 살짝 변경 해야한다.
모두 최선의 플레이를 했다를 구현하기 위해 A의 차례이든, B의 차례이든 각 depth 별 즉 자신의 turn에 자신이 이길 수 있는지 확인하고, 행동하도록 구현한다.
따라서 자신의 turn에 둘 수 있는 경우의 수 중 이기는 수가 하나라면 그것을 선택한다.
이기는 수가 여러 개라면, 그 중에서 turn 수가 가장 짧은 것을 선택한다.
모두 지는 수라면, 그 중에서 turn 수가 가장 긴 것을 선택한다.
구현 끝! 이제 코드를 보러 가볼ㄲ...
🤔 어떻게 자기가 이길지 질지를 아는데요?
중요한 것을 설명 안했다.
각 depth에서 자신이 이길지 질지 아는 것은 현 depth에서 나올 수 있는 각 branch에서 소요된 turn 수가 짝수인가, 홀수인가 확인하는 것이다.
어떤 플레이어가 진다면, 그 결과를 자신의 턴에 확인할 수 있다.
더 이상 갈 곳이 없는지 여부, 자신의 발판이 사라진지 여부는 자신의 depth에서 탐색을 해야지 확인된기 때문이다.
자신의 turn에 졌다면 turn 수는 무조건 짝수이다!!
예를 들어 A -> B -> A(결과: A 패배), A-> B -> A -> B -> A(결과: A 패배) 등이 있다.
현재 의사 판단을 해야하는 자신의 depth(위의 예시의 처음 A)을 제외하고 봐라, 모두 2, 4... turn 수가 짝수다.
따라서 현 Depth에서 진행한 경우의 수(branch) 결과가 짝수이면, 자신의 패배, 반대로 홀수이면 상대편 차례에서 상대편이 더 이상 갈 곳이 없거나 발판이 사라져 떨어져 게임이 끝났음을 의미하기 자신의 승리 이다!
이를 활용한다.
- branch 결과 중 하나라도 홀수이면 그 녀석을 선택 (이기는 게 최적의 플레이)
- branch 결과가 모두 짝수이면 최대값을 선택 (어짜피 질 땐 시간을 제일 많이 끄는 게 최적의 플레이)
- branch 결과가 모두 홀수이면 최소값을 선택 (어짜피 이길 땐 turn 수 최소화가 최적의 플레이)
다음은 내가 위의 과정을 그림으로 그린 것이다. 이해가 안되면 한 번 그려보자. 나도 당최 이해가 안되다가 그림을 그리니 이해가 되었다.
이렇게 하면 플레이어는 양쪽 모두 최선의 플레이만 한 것이기 때문에 문제의 조건을 지키는 것이다. 이제 코드 하나하나 분석해보자.
3. 코드 분석
class Solution {
// 0. 사방탐색 배열, 방문배열, 초기 발판 상태 배열 -> 5개가 최대니까 바로 선언해줬습니다. + 행과 열
int [][] dir = {{-1,0},{0,1},{1,0},{0,-1}};
boolean [][] vis = new boolean [5][5];
int [][] block = new int [5][5];
int r,c;
public int solution(int[][] board, int[] aloc, int[] bloc) {
r = board.length; c = board[0].length;
// 1. 초기 발판 상태 입력 받기
for(int i = 0; i < r; i++){
for(int j = 0; j < c; j++){
block[i][j] = board[i][j];
}
}
return minMax(aloc[0], aloc[1], bloc[0], bloc[1]);
}
// 2. 문제용 재귀함수
public int minMax (int curY, int curX, int opY, int opX) {
// 반환값
int ret = 0;
// (1) 만약 현재 밟고 있는 발판이 사라졌으면 게임 끝이니까 바로 반환
if(vis[curY][curX]) return 0;
// (2) 사방탐색
for(int i = 0; i < 4; i++){
int ny = curY + dir[i][0];
int nx = curX + dir[i][1];
// 범위를 넘어가거나, 이미 방문했거나 벽인 경우 continue
if(OOB(ny,nx) || vis[ny][nx] || block[ny][nx] == 0) continue;
// 현재 밟고 있는 발판을 허공으로 바꾸고, 재귀
vis[curY][curX] = true;
// 현재 turn에서 가능한 경우의 수 중 하나로 가보는 것
int pos = minMax(opY,opX,ny,nx) + 1;
// 해당 분기 탐색 마치면 현 발판은 원래 상태로 고르기
vis[curY][curX] = false;
// ret은 이제까지 모든 분기의 결과값 중 최적의 해
// val은 현재의 해 입니다.
// 현재까지 모든 분기가 패배였는데, 현 분기가 승리인 경우, 승리 분기 선택
if(ret%2 == 0 && pos%2 == 1) ret = pos;
// 현재까지 모든 분기가 패배였는데, 현 분기도 패배인 경우, 가장 turn 수 긴 거 선택
else if(ret%2 == 0 && pos%2 == 0) ret = Math.max(ret,pos);
// 현재까지 모든 분기가 승리였는데, 현 분기도 승리인 경우, 가장 turn 수 짧은 것 선택
else if(ret%2 == 1 && pos%2 == 1) ret = Math.min(ret,pos);
}
return ret;
}
// Out of Bound 잡이
public boolean OOB (int nowY, int nowX){
return (nowY < 0 || nowX < 0 || nowY >=r || nowX >= c);
}
}4. 후기
이거 킬러문항 아닙니까? 너무 어렵네요.
저는 100% 이해하기까지 하루 걸렸습니다. 저처럼 오래 걸린 사람도 있으니, 혹시 풀이 봤다고 주눅들지 마시고 화이팅 합시다...
