문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/92345
코딩테스트 연습 - 사라지는 발판
[[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
programmers.co.kr
문제 설명
플레이어 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 함수를 완성해주세요.
제한사항
- 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이 같을 수 있습니다.
- 상대 플레이어의 캐릭터가 있는 칸으로 이동할 수 있습니다.
입출력 예
입출력 예 설명
입출력 예 #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입니다.
제한시간 안내
- 정확성 테스트 : 10초
풀이
해설 보고 풀었다.
알고리즘 대회에나 나올 법한 '게임 이론' 분류의 문제가 있다고 한다.
나도 종종 백준에서 봤던 것 같은데, 이 문제는 이러한 '게임 이론' 문제의 난이도를 하향해 완전 탐색으로도 풀 수 있게 한 문제이다.
실제로 문제를 읽고, 아.. 최적의 플레이, 최선의 플레이... 어렵다 게임 이론.. 이란 느낌을 팍 받아서 해설을 보지 않고 풀 수 없었다.
통과하고 나서도 이해가 안 돼서 한참 들여다봤다.
무튼 moveA, moveB 이렇게 두 개의 함수가 서로에게 턴을 넘겨가며(서로를 호출) A가 항상 이길 수 있는지, 이길 수 있다면 최소한의 턴(A+B), A가 무조건 진다면 최대한의 턴(A+B)를 리턴한다.
A혹은 B가 항상 이길 수 있는지를 판단하는 것은, 문제에서 주어진 두 개의 기저 사례를 이용해 4방향의 이동 가능한 경우의 수만큼 A가 이겼는지, B가 이겼는지를 반환하는 것으로 알 수 있다.
예를 들어 인접 4방향에 대해 B가 움직이고 A에게 턴을 넘겼을 때 A가 움직인 결과가 하나라도 false(A가 이길 수 없다)가 나온다면,
B는 이길 수 있는 경우의 수가 있으므로 무조건 이기는 선택을 하게 된다.
이 문제에선 A가 먼저 시작하므로, 재귀의 뎁스 0 (첫 함수 호출 부분)에서 canWin이 true면 A가 실수하지 않는 경우 무조건 이기는 판이고, false면 A는 어떻게 해도 지는 판이다.
아래 코드가 핵심이다
val result = move(board, r2, c2, nr, nc,cnt+1)
//상대방이 이길 수 없다는 결과가 나오면 내가 이김
if(!result.first){
//내가 이기는 경우에서 가장 적게 움직이는 값 저장
canWin = true
minTurn = minTurn.coerceAtMost(result.second)
}
else if(!canWin){
//내가 지는 경우에서 가장 많이 움직이는 값 저장
maxTurn = maxTurn.coerceAtLeast(result.second)
}
}
board[r1][c1] = 1
//내가 이긴다면 가장 적은 이동, 내가 진다면 가장 많은 이동을 반환
//내가 이길 수 있다면 무조건 이기는 선택
//a부터 시작하므로, 뎁스 0에서 a의 canWin이 true라면 무조건 a가 이기는 선택을 하게됨
val turn = if(canWin) minTurn else maxTurn
return Pair(canWin,turn+1)이 코드를 문제를 읽고 생각하여 코드로 짜는 것이 쉽지 않았다.
이 외의 부분은 일반적인 재귀(dfs)의 형태로, 구현하기 어렵지 않다.
코드1
class Solution {
val dir = arrayOf(
arrayOf(0,1),
arrayOf(1,0),
arrayOf(0,-1),
arrayOf(-1,0)
)
//누가 이겼는지는 필요 없음
//하지만 아래 함수만으로도 누가 이겼는지를 알 수 있음
fun move(board: Array<IntArray>, r1: Int, c1: Int, r2: Int, c2: Int, cnt: Int): Pair<Boolean,Int>{
//기저사례1
//이동할 수 있는 칸이 없는 경우 현재 유저가 짐
var isFinished = true
for(i in 0 until 4){
val nr = r1 + dir[i][0]
val nc = c1 + dir[i][1]
if(nr !in board.indices || nc !in board[0].indices) continue
if(board[nr][nc]==0) continue
isFinished = false
}
if(isFinished){
return Pair(false,0)
}
//기저사례2
//같은 칸을 밟고 있는 경우 현재 유저가 이김
if(r1 == r2 && c1 == c2){
return Pair(true,1)
}
//현재 있던 칸 0으로 만들고 이동
board[r1][c1] = 0
var canWin = false
var minTurn = Int.MAX_VALUE
var maxTurn = 0
for(i in 0 until 4){
val nr = r1 + dir[i][0]
val nc = c1 + dir[i][1]
if(nr !in board.indices || nc !in board[0].indices) continue
if(board[nr][nc]==0) continue
val result = move(board, r2, c2, nr, nc,cnt+1)
//상대방이 이길수 없다는 결과가 나오면 내가 이김
if(!result.first){
//내가 이기는 경우에서 가장 적게 움직이는 값 저장
canWin = true
minTurn = minTurn.coerceAtMost(result.second)
}
else if(!canWin){
//내가 지는 경우에서 가장 많이 움직이는 값 저장
maxTurn = maxTurn.coerceAtLeast(result.second)
}
}
board[r1][c1] = 1
//내가 이긴다면 가장 적은 이동, 내가 진다면 가장 많은 이동을 반환
//내가 이길 수 있다면 무조건 이기는 선택
//a부터 시작하므로, 뎁스 0에서 a의 canWin이 true라면 무조건 a가 이기는 선택을 하게됨
val turn = if(canWin) minTurn else maxTurn
return Pair(canWin,turn+1)
}
fun solution(board: Array<IntArray>, aloc: IntArray, bloc: IntArray): Int {
return move(board, aloc[0], aloc[1], bloc[0], bloc[1], 0).second
}
}코드2
class Solution {
val dir = arrayOf(
arrayOf(0,1),
arrayOf(1,0),
arrayOf(0,-1),
arrayOf(-1,0)
)
fun moveA(board: Array<IntArray>, aloc: IntArray, bloc: IntArray): Pair<String,Int>{
var isFinished = true
for(i in 0 until 4){
val nr = aloc[0] + dir[i][0]
val nc = aloc[1] + dir[i][1]
if(nr !in board.indices || nc !in board[0].indices) continue
if(board[nr][nc]==0) continue
isFinished = false
}
if(isFinished){
return Pair("b",0)
}
if(board[aloc[0]][aloc[1]] == 0){
return Pair("b",0)
}
board[aloc[0]][aloc[1]] = 0
var canWin = false
var minTurn = Int.MAX_VALUE
var maxTurn = 0
for(i in 0 until 4){
val nr = aloc[0] + dir[i][0]
val nc = aloc[1] + dir[i][1]
if(nr !in board.indices || nc !in board[0].indices) continue
if(board[nr][nc]==0) continue
val result = moveB(board, intArrayOf(nr,nc), bloc )
if(result.first=="a"){
canWin = true
minTurn = minTurn.coerceAtMost(result.second)
}
else if(!canWin){
maxTurn = maxTurn.coerceAtLeast(result.second)
}
}
board[aloc[0]][aloc[1]] = 1
return if(canWin) Pair("a",minTurn+1) else Pair("b",maxTurn+1)
}
fun moveB(board: Array<IntArray>, aloc: IntArray, bloc: IntArray): Pair<String,Int>{
var isFinished = true
for(i in 0 until 4){
val nr = bloc[0] + dir[i][0]
val nc = bloc[1] + dir[i][1]
if(nr !in board.indices || nc !in board[0].indices) continue
if(board[nr][nc]==0) continue
isFinished = false
}
if(isFinished){
return Pair("a",0)
}
//현재 밟고 있던 칸이 0이 된 경우
if(board[bloc[0]][bloc[1]] == 0){
return Pair("a",0)
}
//현재 있던 칸 0으로 만들고 이동
board[bloc[0]][bloc[1]] = 0
var canWin = false
var minTurn = Int.MAX_VALUE
var maxTurn = 0
for(i in 0 until 4){
val nr = bloc[0] + dir[i][0]
val nc = bloc[1] + dir[i][1]
if(nr !in board.indices || nc !in board[0].indices) continue
if(board[nr][nc]==0) continue
val result = moveA(board, aloc, intArrayOf(nr,nc) )
if(result.first=="b"){
canWin = true
minTurn = minTurn.coerceAtMost(result.second)
}
else if(!canWin){
maxTurn = maxTurn.coerceAtLeast(result.second)
}
}
board[bloc[0]][bloc[1]] = 1
return if(canWin) Pair("b",minTurn+1) else Pair("a",maxTurn+1)
}
fun solution(board: Array<IntArray>, aloc: IntArray, bloc: IntArray): Int {
return moveA(board, aloc, bloc).second
}
}'알고리즘 문제 풀이 > 프로그래머스' 카테고리의 다른 글
| 프로그래머스 모음사전 c++, Kotlin (순열) (0) | 2022.06.21 |
|---|---|
| 프로그래머스 이진 변환 반복하기 Kotlin (문자열) (0) | 2022.06.15 |
| 프로그래머스 파괴되지 않은 건물 Kotlin (누적 합) (0) | 2022.05.27 |
| 프로그래머스 징검다리 Kotlin (이분탐색) (0) | 2022.05.25 |
| 프로그래머스 N-Queen Kotlin (백트래킹) (0) | 2022.05.20 |
댓글