백준 12100번 2048(Easy)

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

한번쯤은 봤던 2048게임과 동일하다.

주어진 게임판을 최대 5번 움직여서 얻을 수 있는 가장 큰 숫자를 출력하는 문제이다.

딱히 어려운 내용은 없고, 4 방향에 대한 이동만 잘 구현한 뒤 dfs로 완전탐색 하기로 하였다. (보드가 최대 20x20이므로)

한쪽 방향에 대한 구현만 하면 나머지 방향들은 이중 포문의 i와 j를 바꾸거나, reversed()를 통해 반대로 순회하면 되므로 moveLeft만 설명하겠다.

한 행이 만약 [2, 0, 0, 2, 0, 2, 2]로 주어진다면 [4, 4, 0, 0, 0, 0, 0]으로 변환해야 한다.

내가 생각한 변환 알고리즘은 아래와 같다.

1. prev와 prevIdx라는 변수 두 개를 0으로 선언한다.
2. 행 배열을 순회하며 0이 아닌 숫자가 등장하면 prev에 해당 숫자를, prevIdx에 해당 인덱스를 넣는다. (+다음 숫자가 0이면 continue)
3. prev가 0이 아니고 다음 숫자도 0이 아니라면 두 숫자를 비교한다.
4. 두 숫자가 같으면 prevIdx 위치에 2*prev를 넣고 현재 위치를 0으로 만든다.
5. 두 숫자가 다르면 현재 숫자와 인덱스를 prev와 prevIdx에 넣는다.
6. 모두 순회했으면 0을 제외한 숫자들을 왼쪽으로 당긴다.

var N = 0

fun main(args: Array<String>): Unit = with(System.`in`.bufferedReader()) {
    N = readLine().toInt()
    val map = Array(N){readLine().split(' ').map{it.toInt()}.toTypedArray()}

    var max = 0
    fun dfs(cur: Array<Array<Int>>, cnt: Int){
        if(cnt == 0){
            val mx = findMax(cur)
            if(mx > max) max = mx
            return
        }

        dfs(moveLeft(cur), cnt - 1)
        dfs(moveRight(cur), cnt - 1)
        dfs(moveUp(cur), cnt - 1)
        dfs(moveDown(cur), cnt - 1)
    }
    dfs(map, 5)
    print(max)
}

fun findMax(map: Array<Array<Int>>): Int{
    var max = 0
    for(i in map.indices){
        for(n in map[i]){
            if(n > max) max = n
        }
    }
    return max
}

fun moveLeft(map: Array<Array<Int>>): Array<Array<Int>>{
    val copy = Array(N){Array(N){0}}
    for(i in map.indices)
        copy[i] = map[i].clone()

    for(i in copy.indices){
        var prev = 0
        var prevIdx = 0

        for(j in copy[i].indices){
            if(copy[i][j] == 0) continue

            if(prev != 0 && prev == copy[i][j]){
                copy[i][prevIdx] = 2 * prev
                copy[i][j] = 0
                prev = 0
                prevIdx = 0
            }else{
                prev = copy[i][j]
                prevIdx = j
            }
        }

        var idx = 0
        for(j in copy[i].indices){
            if(copy[i][j] != 0){
                copy[i][idx++] = copy[i][j]
            }
        }
        while(idx < copy[i].size)
            copy[i][idx++] = 0
    }

    return copy
}

fun moveRight(map: Array<Array<Int>>): Array<Array<Int>>{
    val copy = Array(N){Array(N){0}}
    for(i in map.indices)
        copy[i] = map[i].clone()

    for(i in copy.indices){
        var prev = 0
        var prevIdx = 0

        for(j in copy[i].indices.reversed()){
            if(copy[i][j] == 0) continue

            if(prev != 0 && prev == copy[i][j]){
                copy[i][prevIdx] = 2 * prev
                copy[i][j] = 0
                prev = 0
                prevIdx = 0
            }else{
                prev = copy[i][j]
                prevIdx = j
            }
        }

        var idx = N - 1
        for(j in copy[i].indices.reversed()){
            if(copy[i][j] != 0){
                copy[i][idx--] = copy[i][j]
            }
        }
        while(idx >= 0)
            copy[i][idx--] = 0
    }

    return copy
}

fun moveUp(map: Array<Array<Int>>): Array<Array<Int>>{
    val copy = Array(N){Array(N){0}}
    for(i in map.indices)
        copy[i] = map[i].clone()

    for(i in 0 until N){
        var prev = 0
        var prevIdx = 0

        for(j in 0 until N){
            if(copy[j][i] == 0) continue

            if(prev != 0 && prev == copy[j][i]){
                copy[prevIdx][i] = 2 * prev
                copy[j][i] = 0
                prev = 0
                prevIdx = 0
            }else{
                prev = copy[j][i]
                prevIdx = j
            }
        }

        var idx = 0
        for(j in 0 until N){
            if(copy[j][i] != 0){
                copy[idx++][i] = copy[j][i]
            }
        }
        while(idx < N)
            copy[idx++][i] = 0
    }

    return copy
}

fun moveDown(map: Array<Array<Int>>): Array<Array<Int>>{
    val copy = Array(N){Array(N){0}}
    for(i in map.indices)
        copy[i] = map[i].clone()

    for(i in 0 until N){
        var prev = 0
        var prevIdx = 0

        for(j in (0 until N).reversed()){
            if(copy[j][i] == 0) continue

            if(prev != 0 && prev == copy[j][i]){
                copy[prevIdx][i] = 2 * prev
                copy[j][i] = 0
                prev = 0
                prevIdx = 0
            }else{
                prev = copy[j][i]
                prevIdx = j
            }
        }

        var idx = N - 1
        for(j in (0 until N).reversed()){
            if(copy[j][i] != 0){
                copy[idx--][i] = copy[j][i]
            }
        }
        while(idx >= 0)
            copy[idx--][i] = 0
    }

    return copy
}