[Swift] 2022 KAKAO BLIND RECRUITMENT 사라지는 발판

Problem

 

코딩테스트 연습 - 사라지는 발판

---

Solution

 

해당 문제는 완전 탐색으로 풀 수 있는 문제입니다.

 

1. 플레이어의 위치와 게임 끝났을 때 움직인 횟수와 승자를 알려줄 구조체를 만든다.

 

struct Location {
    var x:Int,y:Int
}

struct GameResult {
    var count:Int,isWinnerA:Bool
}

 

2. board의 가장 자리를 0으로 감싸준다.

 

Index out of range 오류를 쉽게 피하기 위해서 입니다.

 

func wrapBoardEdges(_ board:[[Int]]) -> [[Int]] {
    var wrapBoard = board
    for i in 0..<board.count {
        wrapBoard[i].insert(0, at: 0)
        wrapBoard[i].append(0)
    }
    wrapBoard.insert(Array(repeating: 0, count: board[0].count+2), at: 0)
    wrapBoard.append(Array(repeating: 0, count: board[0].count+2))
    return wrapBoard
}

 

3. 왼쪽,오른쪽,위쪽,아래쪽 네 방향으로 움직일 때의 위치를 미리 만들어줄 함수를 구현한다.

 

func makeLRUD(_ loc:Location) -> [Location] {
    return [Location(x: loc.x-1, y: loc.y),Location(x: loc.x+1, y: loc.y),Location(x: loc.x, y: loc.y-1),Location(x: loc.x, y: loc.y+1)]
}

 

4. 플레이어가 번갈아가면서 움직일 move 함수를 만들어 준다.

 

무조건 이기는 플레이어와 지는 플레이어가 존재하므로 이기는 경우와 지는 경우에 최댓값과 최솟값을 달리해주어야 하는데요.

 

만약 무조건 지는 플레이어라면 최대한으로 많이 움직여야 하므로 maxCount를 최댓값을 업데이트 해주고 이기는 플레이어라면

 

최소한으로 움직여야 하므로 minCount를 최솟값으로 업데이트 해줍니다.

 

func move(_ board:[[Int]], _ count:Int,_ aLoc:Location,_ bLoc:Location) -> GameResult {
    let isTurnA = count%2 == 0 ? true : false
    let loc = isTurnA ? aLoc : bLoc
    var minCount = Int.max
    var maxCount = 0
    
    if board[loc.x][loc.y] == 0 {
        return GameResult(count: count, isWinnerA: isTurnA)
    }
        
    for l in makeLRUD(loc).filter({board[$0.x][$0.y] != 0}) {
        var newBoard = board
        newBoard[loc.x][loc.y] = 0
        let moved = isTurnA ? move(newBoard,count+1,l,bLoc) : move(newBoard,count+1,aLoc,l)
        let result = isTurnA ? moved.isWinnerA :!moved.isWinnerA
        if result {
            maxCount = max(maxCount,moved.count)
        }else {
            minCount = min(minCount,moved.count)
        }
    }
    
    if minCount == Int.max && maxCount == 0 {
        return GameResult(count: count, isWinnerA: isTurnA)
    }
    
    if minCount != Int.max {
        return GameResult(count: minCount, isWinnerA: !isTurnA)
    }
    
    return GameResult(count: maxCount, isWinnerA: isTurnA)
}

 

5. 최적의 플레이 값을 반환한다.

 

func solution(_ board:[[Int]], _ aloc:[Int], _ bloc:[Int]) -> Int {
    let wrapBoard = wrapBoardEdges(board)
    let aLoc = Location(x: aloc[0]+1, y: aloc[1]+1)
    let bLoc = Location(x: bloc[0]+1, y: bloc[1]+1)
    let result = move(wrapBoard, 0, aLoc, bLoc)
    return result.count
}

---

Source Code