프로그래머스: 사라지는 발판⭐⭐⭐
카테고리: Programmers
태그: Algorithm, Blog, C++, Programmers
체감 난이도 : ⭐⭐⭐
유형 : minimax
걸린 시간: 1시간 초과!
🧐 문제Permalink
문제 설명Permalink
플레이어 A와 플레이어 B가 서로 게임을 합니다. 당신은 이 게임이 끝날 때까지 양 플레이어가 캐릭터를 몇 번 움직이게 될지 예측하려고 합니다.
각 플레이어는 자신의 캐릭터 하나를 보드 위에 올려놓고 게임을 시작합니다. 게임 보드는 1x1 크기 정사각 격자로 이루어져 있으며, 보드 안에는 발판이 있는 부분과 없는 부분이 있습니다. 발판이 있는 곳에만 캐릭터가 서있을 수 있으며, 처음 캐릭터를 올려놓는 곳은 항상 발판이 있는 곳입니다. 캐릭터는 발판이 있는 곳으로만 이동할 수 있으며, 보드 밖으로 이동할 수 없습니다. 밟고 있던 발판은 그 위에 있던 캐릭터가 다른 곳으로 이동하여 다른 발판을 밞음과 동시에 사라집니다. 양 플레이어는 번갈아가며 자기 차례에 자신의 캐릭터를 상하좌우로 인접한 4개의 칸 중에서 발판이 있는 칸으로 옮겨야 합니다.
다음과 같은 2가지 상황에서 패자와 승자가 정해지며, 게임이 종료됩니다.
- 움직일 차례인데 캐릭터의 상하좌우 주변 4칸이 모두 발판이 없거나 보드 밖이라서 이동할 수 없는 경우, 해당 차례 플레이어는 패배합니다.
- 두 캐릭터가 같은 발판 위에 있을 때, 상대 플레이어의 캐릭터가 다른 발판으로 이동하여 자신의 캐릭터가 서있던 발판이 사라지게 되면 패배합니다.
게임은 항상 플레이어 A가 먼저 시작합니다. 양 플레이어는 최적의 플레이를 합니다. 즉, 이길 수 있는 플레이어는 최대한 빨리 승리하도록 플레이하고, 질 수밖에 없는 플레이어는 최대한 오래 버티도록 플레이합니다. ‘이길 수 있는 플레이어’는 실수만 하지 않는다면 항상 이기는 플레이어를 의미하며, ‘질 수밖에 없는 플레이어’는 최선을 다해도 상대가 실수하지 않으면 항상 질 수밖에 없는 플레이어를 의미합니다. 최대한 오래 버틴다는 것은 양 플레이어가 캐릭터를 움직이는 횟수를 최대화한다는 것을 의미합니다.
아래 그림은 초기 보드의 상태와 각 플레이어의 위치를 나타내는 예시입니다.
위와 같은 경우, 플레이어 A는 실수만 하지 않는다면 항상 이길 수 있습니다. 따라서 플레이어 A는 이길 수 있는 플레이어이며, B는 질 수밖에 없는 플레이어입니다. 다음은 A와 B가 최적의 플레이를 하는 과정을 나타냅니다.
- 플레이어 A가 초기 위치 (1, 0)에서 (1, 1)로 이동합니다. 플레이어 A가 (0, 0)이나 (2, 0)으로 이동할 경우 승리를 보장할 수 없습니다. 따라서 무조건 이길 방법이 있는 (1, 1)로 이동합니다.
- 플레이어 B는 (1, 1)로 이동할 경우, 바로 다음 차례에 A가 위 또는 아래 방향으로 이동하면 발판이 없어져 패배하게 됩니다. 질 수밖에 없는 플레이어는 최대한 오래 버티도록 플레이하기 때문에 (1, 1)로 이동하지 않습니다. (1, 2)에서 위쪽 칸인 (0, 2)로 이동합니다.
- A가 (1, 1)에서 (0, 1)로 이동합니다.
- B에게는 남은 선택지가 (0, 1)밖에 없습니다. 따라서 (0, 2)에서 (0, 1)로 이동합니다.
- A가 (0, 1)에서 (0, 0)으로 이동합니다. 이동을 완료함과 동시에 B가 서있던 (0, 1)의 발판이 사라집니다. B가 패배합니다.
- 만약 과정 2에서 B가 아래쪽 칸인 (2, 2)로 이동하더라도 A는 (2, 1)로 이동하면 됩니다. 이후 B가 (2, 1)로 이동, 다음 차례에 A가 (2, 0)으로 이동하면 B가 패배합니다.
위 예시에서 양 플레이어가 최적의 플레이를 했을 경우, 캐릭터의 이동 횟수 합은 5입니다. 최적의 플레이를 하는 방법은 여러 가지일 수 있으나, 이동한 횟수는 모두 5로 같습니다.
게임 보드의 초기 상태를 나타내는 2차원 정수 배열 board
와 플레이어 A의 캐릭터 초기 위치를 나타내는 정수 배열 aloc
, 플레이어 B의 캐릭터 초기 위치를 나타내는 정수 배열 bloc
이 매개변수로 주어집니다. 양 플레이어가 최적의 플레이를 했을 때, 두 캐릭터가 움직인 횟수의 합을 return 하도록 solution 함수를 완성해주세요.
제한사항Permalink
- 1 ≤
board
의 세로 길이 ≤ 5 - 1 ≤
board
의 가로 길이 ≤ 5 board
의 원소는 0 또는 1입니다.- 0은 발판이 없음을, 1은 발판이 있음을 나타냅니다.
- 게임 보드의 좌측 상단 좌표는 (0, 0), 우측 하단 좌표는 (
board
의 세로 길이 - 1,board
의 가로 길이 - 1)입니다.
aloc
과bloc
은 각각 플레이어 A의 캐릭터와 플레이어 B의 캐릭터 초기 위치를 나타내는 좌표값이며 [r, c] 형태입니다.- r은 몇 번째 행인지를 나타냅니다.
- 0 ≤ r <
board
의 세로 길이 - c는 몇 번째 열인지를 나타냅니다.
- 0 ≤ c <
board
의 가로 길이 - 초기 보드의
aloc
과bloc
위치는 항상 발판이 있는 곳입니다. aloc
과bloc
이 같을 수 있습니다.
- 상대 플레이어의 캐릭터가 있는 칸으로 이동할 수 있습니다.
입출력 예Permalink
board | aloc | bloc | result |
---|---|---|---|
[[1, 1, 1], [1, 1, 1], [1, 1, 1]] | [1, 0] | [1, 2] | 5 |
[[1, 1, 1], [1, 0, 1], [1, 1, 1]] | [1, 0] | [1, 2] | 4 |
[[1, 1, 1, 1, 1]] | [0, 0] | [0, 4] | 4 |
[[1]] | [0, 0] | [0, 0] | 0 |
입출력 예 설명Permalink
접기/펼치기
입출력 예 #1
문제 예시와 같습니다.
입출력 예 #2
주어진 조건을 그림으로 나타내면 아래와 같습니다.

항상 이기는 플레이어는 B, 항상 지는 플레이어는 A입니다.
다음은 B가 이기는 방법 중 하나입니다.
- A가 (1, 0)에서 (0, 0)으로 이동
- B가 (1, 2)에서 (2, 2)로 이동
- A가 (0, 0)에서 (0, 1)로 이동
- B가 (2, 2)에서 (2, 1)로 이동
- A가 (0, 1)에서 (0, 2)로 이동
- B가 (2, 1)에서 (2, 0)으로 이동
A는 더 이상 이동할 수 없어 패배합니다.
위와 같이 플레이할 경우 이동 횟수 6번 만에 게임을 B의 승리로 끝낼 수 있습니다.
B가 다음과 같이 플레이할 경우 게임을 더 빨리 끝낼 수 있습니다. 이길 수 있는 플레이어는 최대한 빨리 게임을 끝내려 하기 때문에 위 방법 대신 아래 방법을 선택합니다.
- A가 (1, 0)에서 (0, 0)으로 이동
- B가 (1, 2)에서 (0, 2)로 이동
- A가 (0, 0)에서 (0, 1)로 이동
- B가 (0, 2)에서 (0, 1)로 이동
A는 더 이상 이동할 수 없어 패배합니다.
위와 같이 플레이할 경우 이동 횟수 4번 만에 게임을 B의 승리로 끝낼 수 있습니다. 따라서 4를 return 합니다.
입출력 예 #3
양 플레이어는 매 차례마다 한 가지 선택지밖에 고를 수 없습니다. 그 결과, (0, 2)에서 어디로도 이동할 수 없는 A가 패배합니다. 양 플레이어가 캐릭터를 움직인 횟수의 합은 4입니다.
입출력 예 #4
게임을 시작하는 플레이어 A가 처음부터 어디로도 이동할 수 없는 상태입니다. 따라서 A의 패배이며, 이동 횟수의 합은 0입니다.
✏️ 풀이 과정Permalink
이 문제는 minimax 알고리즘을 사용하여 풀면 된다.
재귀적으로 갈수 있는 모든 다음 위치를 순회한다.
각 재귀 호출은 게임판 상태를 인자로 받고, 다음 턴 결과를 반환받는다.
재귀에서 돌아올때(역순),
다음 턴의 상대가 이길수 있는 경우가 하나라도 있다면?
→ 나는 질수밖에 없다.
→ 그러므로, 최대한 늦게 지도록 턴 수를 최대화한다.
반대로 다음 턴의 상대가 이길수 있는 경우가 하나도 없다면?
→ 나는 이길수 있다.
→ 이 경우 최대한 빨리 이기도록 턴 수를 최대화하면 된다.
최종적으로 이길 수 있다면, {이김, 최소 턴}을 반환하고,
질 수밖에 없다면, {짐, 최대 턴}을 반환하면 된다.
✏️ 나의 풀이Permalink
#include <bits/stdc++.h>
#include <climits>
using namespace std;
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
pair<bool,int> dfs(vector<vector<int>> board, vector<int> cur, vector<int> opp) {
if(!board[cur[0]][cur[1]]) { // 턴 넘겨받았는데, 발판 X
return {false, 0};
}
bool canWin = false;
int minTurn = INT_MAX, maxTurn = 0;
for(int dir=0; dir<4; dir++) {
int ay = cur[0] + dy[dir], ax = cur[1] + dx[dir];
if(ax<0 || ay<0 || ax>=board[0].size() || ay>=board.size()) continue;
if(!board[ay][ax]) continue;
board[cur[0]][cur[1]] = 0;
auto [opponentWin, turn] = dfs(board, opp, {ay, ax});
if(!opponentWin) {
canWin = true;
minTurn = min(minTurn, turn+1);
} else {
maxTurn = max(maxTurn, turn+1);
}
board[cur[0]][cur[1]] = 1;
}
if(canWin) return {true, minTurn};
else return {false, maxTurn};
}
int solution(vector<vector<int>> board, vector<int> aloc, vector<int> bloc) {
return dfs(board, aloc, bloc).second;
}
✔️ 다른 사람의 풀이Permalink
#include <bits/stdc++.h>
using namespace std;
int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};
int n, m;
bool OOB(int x, int y){
return x<0 || x>=n || y<0 || y>=m;
}
bool vis[5][5]; // 방문 여부(0일 경우 해당 칸이 아직 남아있음을 의미)
vector<vector<int>> block;
// 현재 상태에서 둘 다 최적의 플레이를 할 때 남은 이동 횟수
// 반환 값이 짝수 : 플레이어가 패배함을 의미, 홀수 : 플레이어가 승리함을 의미
// curx, cury : 현재 플레이어의 좌표, opx, opy : 상대 플레이어의 좌표
int solve(int curx, int cury, int opx, int opy){
// 플레이어가 밟고 있는 발판이 사라졌다면
if(vis[curx][cury]) return 0;
int ret = 0;
// 플레이어를 네 방향으로 이동시켜 다음 단계로 진행할 예정
for(int dir = 0; dir < 4; dir++){
int nx = curx + dx[dir];
int ny = cury + dy[dir];
if(OOB(nx,ny) || vis[nx][ny] || !block[nx][ny]) continue;
vis[curx][cury] = 1; // 플레이어가 직전에 있던 곳에 방문 표시를 남김
// 플레이어를 dir 방향으로 이동시켰을 때 턴의 수
// 다음 함수를 호출할 때 opx, opy, nx, ny 순으로 호출해야 함에 주의
int val = solve(opx, opy, nx, ny)+1;
// 방문 표시 해제
vis[curx][cury] = 0;
// 1. 현재 저장된 턴은 패배인데 새로 계산된 턴은 승리인 경우
if(ret % 2 == 0 && val % 2 == 1) ret = val; // 바로 갱신
// 2. 현재 저장된 턴과 새로 계산된 턴이 모두 패배인 경우
else if(ret % 2 == 0 && val % 2 == 0) ret = max(ret, val); // 최대한 늦게 지는걸 선택
// 3. 현재 저장된 턴과 새로 계산된 턴이 모두 승리인 경우
else if(ret % 2 == 1 && val % 2 == 1) ret = min(ret, val); // 최대한 빨리 이기는걸 선택
}
return ret;
}
int solution(vector<vector<int>> board, vector<int> aloc, vector<int> bloc) {
n = board.size();
m = board[0].size();
block = board;
return solve(aloc[0], aloc[1], bloc[0], bloc[1]);
}
🪶 후기Permalink
MiniMax 알고리즘을 모르는 상태로 풀어서 굉장히 힘들었다.
시간을 너무 잡아먹어서, 결국 다른 사람의 도움을 받았다.
조금만 더 생각하는 힘을 기를 필요가 있다.
댓글남기기