[백준/Swift] 12100번: 2048 (easy)

https://www.acmicpc.net/problem/12100

12100번: 2048 (Easy)

 

이 문제는 2 부분으로 나눌 수 있다.

• 5 이동 방향 케이스 구하기
• 이동 구현

처음에는 1번 ~ 5번 움직임을 모두 보려고 했는데 사실 그냥 5번 이동을 봐도 되는 것이다..! 1회 움직이는 것보단 5회 움직이는 게 최댓값이 나올 확률이 높으니까. 그리고 1회에서 최댓값이 나온다고 해도 사실 5회까지 움직이는 건 상관없을 거 같다. 그래서 DFS로 5회를 여러 방향으로 이동시키는 쪽으로 구현했다.

일단 모든 케이스에 대해서 이동을 하고, max value를 구해야 하므로 이동한 뒤의 배열의 다시 초기값으로 돌려줘야 한다. 그래서 tmpStorage에 원래 block 값을 넣어주고 이동 후, 다른 케이스를 진행할 때 block에 tmpStorage를 넣어서 원래대로 복구했다.

이동 구현 방법은 처음에는 for문을 사용해서 하려고 했는데, 배열 queue를 사용해서 0이 아닌 값을 넣어주고 앞에서부터 이동시켜 줬다.
위로 가는 방식만 설명해 보자면,

우선 열을 고정시키고 행을 이동시키면서 진행했다.
아래로 행을 이동시키면서 0이 아닌 칸을 queue에 넣어주고 값을 0으로 변경했다. (어차피 뒤에서 값을 넣어줄 것이니..)
그리고 이제 추출한 값들을 차례대로 이동시켜 다시 넣어줄 것이다.
data에 넣을 값(맨 앞 원소)을 넣고 3가지 경우로 나눴는데

1. 빈칸인 경우, data 넣기
2. 빈칸이 아니고, 해당 원소가 데이터가 같다면 x2 값 넣기
3. 빈칸이 아니고, 같은 데이터도 아니라면 data 넣기

이런 식으로 진행하면 된다!
queue 배열 말고 while 문을 사용해서 해당 방향으로 당기는 방식으로 해도 될 것 같다.

오랜만에 머리 좀 아픈... 한 방향만 제대로 잡으면 쉽게 풀리긴 하지만^..^

import Foundation

/*
 4x4 보드게임
 한번 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동
 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한번의 이동에서 이미 합쳐진 블록은 또다른 블록과 함쳐질 수 없다
 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램. 0은 빈칸
 */

//input
let n = Int(readLine()!)!
var block = [[Int]]()
var answer = 0
for _ in 0..<n {
    block.append(readLine()!.split(separator: " ").map{ Int(String($0))! })
}

//상:0, 하:1, 좌:2, 우:3
func movingBlock(_ d: Int, _ block: inout [[Int]]) {
    var queue = [Int]()

    if d == 0 { //상
        //같은 열(i)
        for i in 0..<n {
            //이동 행(j)
            for j in 0..<n {
                if block[j][i] != 0 {
                    queue.append(block[j][i]) //0이 아닌 애들만 queue에 넣어준다.
                }
                block[j][i] = 0 //일단 0으로 변경
            }
            var indx = 0

            while !queue.isEmpty {
                let data = queue.first!
                queue.removeFirst()

                if block[indx][i] == 0 { //빈칸인 경우 데이터 넣기
                    block[indx][i] = data
                }else if block[indx][i] == data { //데이터가 같으면 *2 하기!
                    block[indx][i] *= 2
                    indx += 1 //다음 행으로 이동
                }else { //빈칸도 아니고, 같은 데이터도 아니라면 데이터 넣기
                    indx += 1 //다음 행으로 이동
                    block[indx][i] = data
                }
            }
        }
    }else if d == 1 { //하
        for i in 0..<n {
            for j in (0..<n).reversed() {
                if block[j][i] != 0 {
                    queue.append(block[j][i])
                }
                block[j][i] = 0
            }
            var indx = n-1

            while !queue.isEmpty {
                let data = queue.first!
                queue.removeFirst()

                if block[indx][i] == 0 {
                    block[indx][i] = data
                }else if block[indx][i] == data {
                    block[indx][i] *= 2
                    indx -= 1
                }else {
                    indx -= 1
                    block[indx][i] = data
                }
            }
        }
    }else if d == 2 { //좌
        for i in 0..<n {
            for j in 0..<n {
                if block[i][j] != 0 {
                    queue.append(block[i][j])
                }
                block[i][j] = 0
            }
            var indx = 0

            while !queue.isEmpty {
                let data = queue.first!
                queue.removeFirst()

                if block[i][indx] == 0 {
                    block[i][indx] = data
                }else if block[i][indx] == data {
                    block[i][indx] *= 2
                    indx += 1
                }else {
                    indx += 1
                    block[i][indx] = data
                }
            }
        }
    }else { //우
        for i in 0..<n {
            for j in (0..<n).reversed() {
                if block[i][j] != 0 {
                    queue.append(block[i][j])
                }
                block[i][j] = 0
            }
            var indx = n-1

            while !queue.isEmpty {
                let data = queue.first!
                queue.removeFirst()

                if block[i][indx] == 0 {
                    block[i][indx] = data
                }else if block[i][indx] == data {
                    block[i][indx] *= 2
                    indx -= 1
                }else {
                    indx -= 1
                    block[i][indx] = data
                }
            }
        }
    }
}

func DFS(_ now: Int, _ block: inout [[Int]]) {
    if now == 5 { //최대 5회 이동
        for i in 0..<n {
            for j in 0..<n {
                answer = max(answer, block[i][j])
            }
        }
        return
    }
    let tmpStorage = block
    for i in 0...3 {
        movingBlock(i, &block)
        DFS(now + 1, &block)
        block = tmpStorage //원래대로 복구 -> 다른 케이스 적용하기 위해
    }
}

DFS(0, &block)
print(answer)