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

문제 접근 & 문제 풀이

사실 완전 탐색이라는 것은 느낌이 왔다. 왜냐하면 최대가 5*5 짜리 발판이기 때문이다. 

이러면 시간초과가 나는 일을 없을 것이라 생각이 들었다. 하지만 50% 이상 점수 맞기가 힘들었다. 

결국은 못 풀고 해설지를 봤다. 음... 문제를 해석하고 그 해석을 코드를 얼마나 잘 구현하냐가 이 문제의 관건인것 같다.

그래서 이번에는 문제 풀이와 접근을 같이하려고 한다.

전체 코드

import Foundation

func solution(_ board:[[Int]], _ aloc:[Int], _ bloc:[Int]) -> Int {
    let maxY = board.count - 1
    let maxX = board[0].count - 1
    let dy = [1, -1, 0, 0]
    let dx = [0, 0, 1, -1]
    
    func play(_ board: [[Int]], _ aloc: (Int, Int), _ bloc: (Int, Int), _ turn: Int) -> Int {
        let (y, x) = turn == 0 ? aloc : bloc
        
        if board[y][x] == 0 {
            return 0
        }
        var board = board
        board[y][x] = 0
        var count: Int // 새로 기록할 경기
        var ret = 0 // 이전 경기
        for i in 0 ..< 4 {
            let ny = y + dy[i]
            let nx = x + dx[i]
            
            guard ny <= maxY, ny >= 0, nx <= maxX, nx >= 0, board[ny][nx] == 1 else { continue }
            
            if turn == 0 {
                count = 1 + play(board, (ny, nx), bloc, 1)
            } else {
                count = 1 + play(board, aloc, (ny, nx), 0)
            }
            
            if ret == 0 {
                ret = count
            } else if ret % 2 == 0 && count % 2 == 1 {
                ret = count
            } else if ret % 2 == 1 && count % 2 == 1 {
                ret = min(ret, count)
            } else if ret % 2 == 0 && count % 2 == 0 {
                ret = max(ret, count)
            } else if ret % 2 == 1 && count % 2 == 0 {
                // 아무것도 없다
            }
        }
        
        return ret
    }
    
    
    return play(board, (aloc[0], aloc[1]), (bloc[0], bloc[1]), 0)
}

먼저 

func play(_ board: [[Int]], _ aloc: (Int, Int), _ bloc: (Int, Int), _ turn: Int) -> Int

위 함수를 보면 turn은 0 일 때 A가 움직이고 1 일 때 B가 움직일 차례라는 뜻이다.

중요한건 반환되는 Int의 값이다. 이 값은 A / B 상관 없이 자신 시작 기준으로 몇 번을 뒀는지 반환 하는 값이다.

이 값으로 자신이 승리할 것인지 실패할 것인지 알 수 있다.

왜냐하면 자신이 움직이는 순서는 반드시 홀수 이기 떄문이다. 

만약 움직인 횟수가 짝수라면 플레이어가 움직여야 할 타이밍인데 움직이지 못하고 끝났다.이기 때문이다.

* 여기서 플레이어는 A / B 상관하지 않는다.

if ret == 0 {
    ret = count
} else if ret % 2 == 0 && count % 2 == 1 {
    ret = count
} else if ret % 2 == 1 && count % 2 == 1 {
    ret = min(ret, count)
} else if ret % 2 == 0 && count % 2 == 0 {
    ret = max(ret, count)
} else if ret % 2 == 1 && count % 2 == 0 {
    // 아무것도 없다
}

그래서 이 부분을 보면 이해가 간다. ( 승부 == 움직인 횟수)

1. ret == 0
   아직 승부가 결정되지 않았다는 뜻이다. 그러므로 승부를 기록해줘야 한다.
2. ret % 2 == 0 && count % 2 == 1
   이전 데이터 기반 승부는 패배였지만 새로운 경우의 수에서는 승리를 가져 올 수 있다. -> 그러므로 승리로 기록해 줘야 한다.
   => ret = count
3. ret == 1 && count % 2 == 1
   이전 데이터도 새로운 경우의 수도 모두 승리하는 경우이다. 이 때는 최솟값으로 이기는데 힘써야 하므로 최솟값을 쓴다.
   => ret = min(ret, count)
4. ret % 2 == 0 && count % 2 == 0 
   이전 데이터도 새로운 경우의 수도 모두 패배하는 경우이다. 이 때는 최대한 움직이는데 힘써야 하므로 최댓값을 쓴다.
   => ret = max(ret, count)
5. ret % 2 == 1 && count % 2 == 0
   이전 데이터는 승리인데 새로운 경우의 수는 패배이다. 이럴 경우 굳이 건드릴 필요가 없다.

문제 후기

음 문제 난이도는 확실히 Level 3 는 넘어보인다.

양 플레이어는 최적의 플레이를 합니다. 

위 말을 어떻게 코드로 표현하는지가 문제의 Key Point였지 않나 싶다.

 

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