백준 12100 2408(easy)

출처: www.acmicpc.net/problem/12100

분류: 시뮬레이션

---

접근방식

바킹독님의 유튜브 강의를 참고했습니다. 최고 🥰

2048.. 하는 건 좋아했는데 막상 만들라고 하니 꽤 어려웠습니다.

하지만 항상 지나고 생각해보면 그리 어렵지 않습니다 💪

한 행만 잘 합칠 수 있다면 이걸 반복하고, 회전시켜서 간단하게 해결했습니다.

 

한 행 기울이기

먼저 한 행을 왼쪽으로 기울여서 합치는 걸 생각해보겠습니다. 
저는 합쳐진 새로운 행을 만들어 나간다고 생각을 했는데요,

왼쪽으로 기울일거니까 합칠 배열의 인덱스를 0으로 두고 기존의 행을 돌면서 새로운 배열을 만들어 나갔습니다.

새로 만들어질 배열을 mixed, mixed의 현재 인덱스를 movingPoint 라고 해볼게요.
mixed 를 기존 행의 크기에 맞춰 0으로 초기화시켜줍니다.

기존 행의 원소를 r 이라고 하면, 합칠 때는 다음과 같은 경우들을 생각해볼 수 있습니다.

1. mixed의 movingPoint가 0이면 그대로 이동한다. ( mixed[movingPoint] = r )

2. mixed의 movingPoint가 r과 같으면 *2를 해주고 movingPoint를 1 증가시킨다.
( 이미 합쳐진 블록은 다시 합쳐질 수 없다고 문제에 명시되어 있습니다. 따라서 현재 movingPoint는 더 이상 작업이 불가능하니 증가시켜줍니다. )

3. mixed의 movingPoint가 r과 다르면 movingPoint를 1 증가시키고 이동시킨다.

위 과정을 코드로 나타내면 다음과 같습니다.

if mixed[movingPoint] == 0 {
    mixed[movingPoint] = r
} else if mixed[movingPoint] == r {
    mixed[movingPoint] *= 2
    movingPoint += 1
} else {
    movingPoint += 1
    mixed[movingPoint] = r
}

 

회전시키기

이제 저희는 왼쪽으로 기울이는 방법을 알고 있습니다.
나머지 위, 오른쪽, 아래로 기울이는 과정도 비슷한 방식으로 해결해볼 수 있을텐데요,

회전이라는 간단한 아이디어로 왼쪽으로 기울이는 방법을 이용해 나머지도 해결해줄 수 있습니다.

오른쪽 방향으로 기울이기는 90도씩 오른쪽으로 두 번 회전시키면 왼쪽으로 기울이기를 사용해 합쳐줄 수 있습니다.

위는 세 번, 아래는 한 번만 회전시켜주면 되겠네요 :)

회전 시키는 방법은 스티커 붙이기에서 알아봤는데요 이걸 그대로 사용했습니다.

func rotateRightAngle(_ metrix: [[Int]]) -> [[Int]] {
    let rowSize = metrix.count
    let colSize = metrix[0].count
    var rotated = [[Int]](repeating: [Int](repeating: 0, count: rowSize), count: colSize)
    
    for r in 0..<rowSize {
        for c in 0..<colSize {
            rotated[c][rowSize-r-1] = metrix[r][c]
        }
    }
    return rotated
}

 

이제 남은 건 보드를 원하는 대로 회전시키고, 각 행을 합쳐주고를 반복해주면 됩니다.

5번씩 모든 방향을 탐색하는 건 재귀적으로 해줬습니다.

var maxCount = 0
func searchMax(_ metrix: [[Int]], count: Int) {
    guard count < 5 else {
        metrix.forEach {
            $0.forEach {
                maxCount = max(maxCount, $0)
            }
        }
        return
    }
    
    for dir in Direction.allCases {
        let tilted = tilt(metrix, to: dir)
        searchMax(tilted, count: count+1)
    }
}

 

해결방법

// 12100 2048(easy)

enum Direction: CaseIterable {
    case up
    case down
    case left
    case right
    
    var rotateCountToBeLeft: Int {
        switch self {
            case .up: return 3
            case .down: return 1
            case .left: return 0
            case .right: return 2
        }
    }
}

func rotateRightAngle(_ metrix: [[Int]]) -> [[Int]] {
    let rowSize = metrix.count
    let colSize = metrix[0].count
    var rotated = [[Int]](repeating: [Int](repeating: 0, count: rowSize), count: colSize)
    
    for r in 0..<rowSize {
        for c in 0..<colSize {
            rotated[c][rowSize-r-1] = metrix[r][c]
        }
    }
    return rotated
}

func tilt(_ metrix: [[Int]], to dir: Direction) -> [[Int]] {
    var tilted = metrix
    (0..<dir.rotateCountToBeLeft).forEach { _ in
        tilted = rotateRightAngle(tilted)
    }
    
    for row in tilted.indices {
        var mixed = [Int](repeating: 0, count: tilted[row].count)
        var movingPoint = 0
        
        for r in tilted[row] {
            guard r != 0 else { continue }
            if mixed[movingPoint] == 0 {
                mixed[movingPoint] = r
            } else if mixed[movingPoint] == r {
                mixed[movingPoint] *= 2
                movingPoint += 1
            } else {
                movingPoint += 1
                mixed[movingPoint] = r
            }
        }
        
        tilted[row] = mixed
    }
    
    (0..<(4-dir.rotateCountToBeLeft) % 4).forEach { _ in
        tilted = rotateRightAngle(tilted)
    }
    return tilted
}

let n = Int(readLine()!)!
var metrix = [[Int]]()

for _ in 0..<n {
    metrix.append(readLine()!.split(separator: " ").map({ Int($0)! }))
}

var maxCount = 0
func searchMax(_ metrix: [[Int]], count: Int) {
    guard count < 5 else {
        metrix.forEach {
            $0.forEach {
                maxCount = max(maxCount, $0)
            }
        }
        return
    }
    
    for dir in Direction.allCases {
        let tilted = tilt(metrix, to: dir)
        searchMax(tilted, count: count+1)
    }
}

searchMax(metrix, count: 0)
print(maxCount)

 

배운점

좋은 걸 또 배워간다... 

시뮬레이션은 코드량이 너무 많아서 매번 진이 빠진다... ㅜ-ㅜ 

그래도 조금씩 발전하고는 있는듯!