백준 12100번 2048 (Easy) - 스위프트(Swift) 풀이 + 그림 설명

---

 

1. 미는 방향으로 블록을 몬다.
2. 인접한 두 블록을 미는 방향으로 합칠 수 있으면 합친다.
3. 합치면서 생긴 빈자리를 없앤다.
4. 4^5가지 경우에 대해 전부 다 시뮬레이션(1-3과정)하여 최댓값을 구한다.

 

1. 미는 방향으로 블록을 몬다.

 아래와 같은 보드 상태에서 위로 밀어야 하는 상황이다. 열 별로 차례로 밀어줄 것이다. 1열부터 밀어보자. 먼저 빈 공간이 없도록 윗방향으로 블록들을 몰아준다.

 

 

2. 인접한 두 블록을 미는 방향으로 합칠 수 있으면 합친다.

 이제 합칠 차례이다. 만약 인접한 두 블록을 합칠 수 있는 경우 합친다. 미는 방향이 윗방향이기 때문에 윗블록이 남고 아랫 블록은 사라진다.

 

3. 합치면서 생긴 빈자리를 없앤다.

 합치면서 생긴 빈자리를 또 메꿔주면 미는 작업이 끝난다. 나머지 열에 대해서도 모두 1-3과정을 수행해주면 된다.

 

 

4. 4^5가지 경우에 대해 전부 다 시뮬레이션(1-3과정)하여 최댓값을 구한다.

 미는 경우의 수는 4방향 * 5번으로 4^5이다. 시뮬레이션이 O(N^2)의 시간복잡도를 가지고 N=20이므로 브루트포스로도 시간 내에 통과가 가능하다. 모든 경우를 다 시뮬레이션하여 최댓값을 구하면 된다.

반응형

---

import Foundation

var N = 0, result = 0
var board = [[Int]]()

enum Direction: CaseIterable {
    case up, down, left, right
}

func swipe(direction: Direction, state: [[Int]]) -> [[Int]] {
    var swipedState = state
    
    for i in 0..<N {                    // 한 행/열씩 민다.
        let originalColOrRow: [Int]
        switch direction {
        case .left: originalColOrRow = state[i]
        case .right: originalColOrRow = state[i].reversed()
        case .up: originalColOrRow = (0..<N).map{ state[$0][i] }
        case .down: originalColOrRow = (0..<N).reversed().map{ state[$0][i] }
        }
        
        // 1. 한 방향으로 몰기
        var newColOrRow = originalColOrRow.filter{ $0 != 0 }
        
        guard !newColOrRow.isEmpty else { continue }
        
        // 2. 합치기
        for j in 0..<newColOrRow.count-1 {
            guard newColOrRow[j] == newColOrRow[j+1] else { continue }
            newColOrRow[j] *= 2
            newColOrRow[j+1] = 0
        }
        
        // 3. 빈자리 처리
        newColOrRow = newColOrRow.filter{ $0 != 0 }
        while newColOrRow.count < N { newColOrRow.append(0) }
        
        // 4. 결과 복사
        switch direction {
        case .left: swipedState[i] = newColOrRow
        case .right: swipedState[i] = newColOrRow.reversed()
        case .up: (0..<N).forEach{ swipedState[$0][i] = newColOrRow[$0] }
        case .down: (0..<N).forEach{ swipedState[N-1-$0][i] = newColOrRow[$0] }
        }
    }
    
    return swipedState
}

func findMax(_ state: [[Int]]) {
    for i in 0..<N {
        for j in 0..<N {
            result = max(result, state[i][j])
        }
    }
}

func simulate(depth: Int, state: [[Int]]) {
    if depth > 5 { findMax(state); return }

    for direction in Direction.allCases {
        let swipedState = swipe(direction: direction, state: state)
        simulate(depth: depth + 1, state: swipedState)
    }
}

func solution() {
    N = Int(readLine()!)!
    
    for _ in 0..<N {
        board.append(readLine()!.split(separator: " ").map{ Int(String($0))! })
    }
    
    simulate(depth: 1, state: board)
    
    print(result)
}

solution()