[프로그래머스] Swift - 사라지는 발판

https://school.programmers.co.kr/learn/courses/30/lessons/92345

프로그래머스

 

2024.01.14 기준 Level 3

 

알고리즘 공부를 위해 풀고 기록하는 글입니다!
참고만 해주시고 더 좋은 풀이법이 있다면 알려주세요!

 

아이디어

문제 조건

• 2차원 배열 board와 a의 위치, b의 위치가 주어진다.
• a와 b는 자신의 차례가 오면 한칸씩 이동해야 한다.
• 숫자가 1이고 현재 본인의 위치에서 상하좌우에 해당되는 칸으로만 이동 가능하다.
• 이동하면 원래 자리는 발판이 사라진다. (== 숫자가 0으로 바뀐다)
• 이길 수 있는 플레이어는 최대한 빨리 승리하도록 플레이하고 질 수 밖에 없는 플레이어는 최대한 오래 버티도록 플레이한다.
• 이 때 양 플레이어가 최적의 플레이를 했을 때, 두 캐릭터가 움직인 횟수의 합을 리턴하자

 

문제 조건이 꽤나 복잡하다.

요약하면 각 플레이어는 주어진 상황에서 최선의 선택을 해야 한다는 것이다.

 

이걸 위해서는 해당 플레이어에게 승리 가능성이 있는지 없는지가 중요하다.

 

만약 게임을 진행하다가 특정 플레이어에게 승리 가능성이 없다고 결론이 나오면 최대한 늦게 지는 쪽으로 이동해야 한다.

만약 낮은 가능성이라도 승리할 수 있는 경우의 수가 있다면 최대한 빨리 끝내는 경우의 수를 선택해야 한다.

 

 

board의 크기가 최대 5x5이기 때문에 모든 경우의 수를 탐색하는 완전 탐색으로 문제를 해결할 수 있다.

 

dfs를 활용해서 모든 이동 경우의 수를 탐색한다.

 

이 때 dfs 함수는 재귀를 통해 모든 경우의 수를 탐색하게 되고 해당 플레이어의 승리 여부와 총 이동 횟수를 리턴하게 된다.

 

즉, dfs가 dsf를 연쇄적으로 호출하는데 만약 승리가 가능한 경우의 수가 발견되면 현재까지 발견한 이동 횟수 중에서 최솟값을 리턴한다.

모든 경우에서 승리가 불가능하다면 현재까지 발견한 이동 횟수 중에서 최댓값을 리턴한다.

 

움직인 후에는 board에서 원래 위치를 0으로 바꾸어 발판이 사라졌다는 것을 기록한다.

 

 

 

풀이

1. MoveResult 구조체

fileprivate struct MoveResult {
    let isWin: Bool
    let moveCount: Int
}

 

dfs 함수가 리턴할 타입이다.

이 dfs 함수가 움직일 플레이어의 승리 여부와 총 이동 횟수를 저장한다.

 

2. dfs 함수 구현

// 현재 이동 대상인 유저가 승리하면 MoveResult의 isWin이 true를 리턴
fileprivate func dfs(ax: Int, ay: Int, bx: Int, by: Int, board: [[Int]], aTurn: Bool, totalCount: Int) -> MoveResult {
    var board = board
    var winCount = board.count * board[0].count
    var loseCount = totalCount
    var willWin = false
    
    let dx = [0, 0, 1, -1]
    let dy = [1, -1, 0, 0]
    
    if aTurn && board[ax][ay] == 1 { // a가 움직일 차례
        for i in 0..<4 {
            let nx = ax + dx[i]
            let ny = ay + dy[i]
            
            if !isInRange(x: nx, y: ny, board: board) || board[nx][ny] == 0 { continue }
            
            board[ax][ay] = 0
            
            let res = dfs(ax: nx, ay: ny, bx: bx, by: by, board: board, aTurn: false, totalCount: totalCount + 1)
            
            if willWin != true {
                willWin = !res.isWin
            }
            
            if res.isWin {
                loseCount = max(loseCount, res.moveCount)
            } else {
                winCount = min(winCount, res.moveCount)
            }
        }
    }
    
    if !aTurn && board[bx][by] == 1 { // b가 움직일 차례
        for i in 0..<4 {
            let nx = bx + dx[i]
            let ny = by + dy[i]
            
            if !isInRange(x: nx, y: ny, board: board) || board[nx][ny] == 0 { continue }
            
            board[bx][by] = 0
            
            let res = dfs(ax: ax, ay: ay, bx: nx, by: ny, board: board, aTurn: true, totalCount: totalCount + 1)
            
            if willWin != true {
                willWin = !res.isWin
            }
            
            if res.isWin {
                loseCount = max(loseCount, res.moveCount)
            } else {
                winCount = min(winCount, res.moveCount)
            }
        }
    }
    
    return MoveResult(isWin: willWin, moveCount: willWin ? winCount : loseCount)
}

 

aTurn 변수를 통해 a의 차례인지 b의 차례인지 분기한다.

 

이길 수 있는 경우의 수가 발견되면 moveCount의 최솟값을 선택한다.

이길 수 있는 경우가 아예 없다면 moveCount의 최댓값을 선택한다.

3. solution 함수 구현

fileprivate func solution(_ board:[[Int]], _ aloc:[Int], _ bloc:[Int]) -> Int {
    return dfs(ax: aloc[0], ay: aloc[1], bx: bloc[0], by: bloc[1], board: board, aTurn: true, totalCount: 0).moveCount
}

 

dfs 함수를 호출하고 moveCount를 리턴한다.

 

 

마무리

dfs와 백트래킹에 대한 이해가 필요했다.

그리고 항상 최적의 선택을 해야 한다는 조건에 맞추어 현재 상황에서 가능한 경우의 수를 전부 탐색하여 자신의 승리 가능성을 구해야 했다.

이 승리 가능성에 따라 최댓값을 선택할지 최솟값을 선택할지를 나누는 것이 핵심 아이디어였다.

 

꽤나 어려운 문제여서 다른 사람들의 풀이법들도 보고 이해하려고 노력했다.