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

빡구현 문제다.
빡구현 문제는 보통 일반 구현 문제를 2개 혹은 3개를 짬뽕시켰다고 생각하면 되기 때문에
구현하기 전에 기능 구현할 목록을 잘 작성하는 것이 좋다.

나는 다음과 같이 쪼개서 순서대로 문제를 풀었다.

• : dfs 구현
• : 블록 이동, 합치기
• : 블록이 없는 곳까지 이동시킨다

block move/merge 관련 로직

• : 숫자가 다르면 정지
• : 이미 합쳐진 블록이면 정지
• : 합친 후 break
• : graph 에서 가장 큰 값 찾기

1) 백트래킹

• 최대 5번 dfs를 돌린고, 각 depth마다 동서남북으로 블록을 move시킨다.
• depth가 5에 도달하면 ans 값을 갱신시켜 준다.

private fun dfs(blocks: List<IntArray>, depth: Int = 0, dirs: String = "") {
    if (depth == 5) {
        ans = maxOf(ans, blocks.max())
        return
    }

    repeat(4) { i ->
        val copyBlocks = blocks.map { it.copyOf() }
        move(copyBlocks, i)
        dfs(copyBlocks, depth + 1, dirs + i)
    }
}

private fun List<IntArray>.max(): Int {
    return flatMap { it.toList() }.max()
}

2) 블록 움직이고 합치기

params로 받은 dir(방향값)에 따라 분기처리 해준 후, 블록들을 방향에 따라 움직여주고, 합쳐준다.

아래와 같은 분기처리를 통해 블록을 움직이고 합쳤다.(아래 코드는 위(북) 방향에 해당한다)

private fun move(blocks: List<IntArray>, dir: Int) {
    val isMerge = Array(N) { BooleanArray(N) }
    when (dir) {
        // 위
        0 -> {
            for (i in 0 until N) {
                for (j in 0 until N) {
                    // 1) 해당 지역에 block이 있나?
                    if (blocks[i][j] == 0) continue
                    // 2) 블록 움직이기
                    for (cur in i downTo 1) { // cur은 현재 x축 위치
                        val next = cur - 1 // 블록을 움직일 x축 위치
                        
                        // 2 - 0) next가 0이면 이동한다.
                        if (blocks[next][j] == 0) {
                            blocks[next][j] = blocks[cur][j]
                            blocks[cur][j] = 0
                            continue
                        }
                        // 2 - 1) cur과 next 위치의 숫자가 다르면 정지
                        if (blocks[next][j] != blocks[cur][j]) break
                        // 2 - 2) next 위치에 있는 블록이 이미 합쳐진 정지
                        if (isMerge[next][j]) break
                        // 2 - 3) 합치기
                        isMerge[next][j] = true
                        blocks[next][j] *= 2
                        blocks[cur][j] = 0
                        break // 🤬 처음에 여기에 break문을 추가 안해줘서 상당히 고생했다..
                    }
                }
            }
       ...

처음에 위에 실수로 break문을 추가 안해줘서 몇 시간 동안 고생했다..

break문을 추가 안해주면 아래와 같은 오류가 발생한다

ex) 현재 블록을 아래 블록을 <- 방향으로 move시킨다고 가정
  
 (init)  	(정답)		(error!!)
0 4 2 2     4 4 0 0		8 0 0 0
0 0 0 0		0 0 0 0   	0 0 0 0
0 0 0 0		0 0 0 0		0 0 0 0
0 0 0 0		0 0 0 0		0 0 0 0

0 4 2 2 가 4 4 0 0 이 되야 하는데 break를 안해서 8 0 0 0 이 되버림..

반례

참고 : https://forward-gradually.tistory.com/83

10
16 16 8 32 32 0 0 8 8 8
16 0 0 0 0 8 0 0 0 16
0 0 0 0 0 0 0 0 0 2
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

Ans : 64
—————————

10
0 0 64 32 32 0 0 0 0 0
0 32 32 64 0 0 0 0 0 0
0 0 128 0 0 0 0 0 0 0
64 64 128 0 0 0 0 0 0 0
0 0 64 32 32 0 0 0 0 0
0 32 32 64 0 0 0 0 0 0
0 0 128 0 0 0 0 0 0 0
64 64 128 0 0 0 0 0 0 0
128 32 2 4 0 0 0 0 0 0
0 0 128 0 0 0 0 0 0 0

Ans : 1024
—————————

전체 코드

// N : 블록 크기 1 .. 20
// 블록 움직이는 총 경우의 수 4 ** 5 = 1024
// [] : 블록 이동, 합치기
// 1) 블록이 없는 곳까지 이동시킨다
// 2) 블록을 만난다.
// 2 - 1) 숫자가 다르면 정지
// 2 - 2) 이미 합쳐진 블록이면 정지
// 2 - 3) 합친 후 break
// [x] : graph 에서 가장 큰 값 찾기

private var N = 0
private var ans = 0
fun main() {
    N = readln().toInt()
    val blocks = List(N) {
        readln().split(" ").map { it.toInt() }.toIntArray()
    }
    val cop = blocks.map { it.copyOf() }
    move(blocks, 1)
    dfs(cop)
    println(ans)
}

// traverse
private fun dfs(blocks: List<IntArray>, depth: Int = 0, dirs: String = "") {
    if (depth == 5) {
        ans = maxOf(ans, blocks.max())
        return
    }

    repeat(4) { i ->
        val copyBlocks = blocks.map { it.copyOf() }
        move(copyBlocks, i)
        dfs(copyBlocks, depth + 1, dirs + i)
    }
}
// move

private fun move(blocks: List<IntArray>, dir: Int) {
    val isMerge = Array(N) { BooleanArray(N) }
    when (dir) {
        // 위
        0 -> {
            for (i in 0 until N) {
                for (j in 0 until N) {
                    // 1) block인가?
                    if (blocks[i][j] == 0) continue
                    // move
                    for (cur in i downTo 1) {
                        val next = cur - 1
                        // 2 - 0) next가 0이면 이동
                        if (blocks[next][j] == 0) {
                            blocks[next][j] = blocks[cur][j]
                            blocks[cur][j] = 0
                            continue
                        }
                        // 2 - 1) 숫자가 다르면 정지
                        if (blocks[next][j] != blocks[cur][j]) break
                        // 2 - 2) 이미 합쳐진 블록이면 정지
                        if (isMerge[next][j]) break
                        // 2 - 3) 합치기
                        isMerge[next][j] = true
                        blocks[next][j] *= 2
                        blocks[cur][j] = 0
                        break
                    }
                }
            }
        }
        // 오른쪽
        1 -> {
            for (j in N - 1 downTo 0) {
                for (i in 0 until N) {
                    // 1) block인가?
                    if (blocks[i][j] == 0) continue
                    // move
                    for (cur in j until N - 1) {
                        val next = cur + 1
                        // 2 - 0) 0이면 이동
                        if (blocks[i][next] == 0) {
                            blocks[i][next] = blocks[i][cur]
                            blocks[i][cur] = 0
                            continue
                        }
                        // 2 - 1) 숫자가 다르면 정지
                        if (blocks[i][next] != blocks[i][cur]) break
                        // 2 - 2) 이미 합쳐진 블록이면 정지
                        if (isMerge[i][next]) break
                        // 2 - 3) 합치기
                        isMerge[i][next] = true
                        blocks[i][next] *= 2
                        blocks[i][cur] = 0
                        break
                    }
                }
            }
        }
        // 아래
        2 -> {
            for (i in N - 1 downTo 0) {
                for (j in 0 until N) {
                    // 1) block인가?
                    if (blocks[i][j] == 0) continue
                    // move
                    for (cur in i until N - 1) {
                        val next = cur + 1
                        // 2 - 0) 0이면 이동
                        if (blocks[next][j] == 0) {
                            blocks[next][j] = blocks[cur][j]
                            blocks[cur][j] = 0
                            continue
                        }
                        // 2 - 1) 숫자가 다르면 정지
                        if (blocks[next][j] != blocks[cur][j]) break
                        // 2 - 2) 이미 합쳐진 블록이면 정지
                        if (isMerge[next][j]) break
                        // 2 - 3) 합치기
                        isMerge[next][j] = true
                        blocks[next][j] *= 2
                        blocks[cur][j] = 0
                        break
                    }
                }
            }
        }
        // 왼쪽
        3 -> {
            for (j in 0 until N) {
                for (i in 0 until N) {
                    // 1) block인가 ?
                    if (blocks[i][j] == 0) continue
                    // move
                    for (cur in j downTo 1) {
                        val next = cur - 1
                        // 2 - 0) 0이면 이동
                        if (blocks[i][next] == 0) {
                            blocks[i][next] = blocks[i][cur]
                            blocks[i][cur] = 0
                            continue
                        }
                        // 2 - 1) 숫자가 다르면 정지
                        if (blocks[i][next] != blocks[i][cur]) break
                        // 2 - 2) 이미 합쳐진 블록이면 정지
                        if (isMerge[i][next]) break
                        // 2 - 3) 합치기
                        isMerge[i][next] = true
                        blocks[i][next] *= 2
                        blocks[i][cur] = 0
                        break // <= 이거 때메 안된 거였음
                    }
                }
            }
        }
    }
}

private fun List<IntArray>.max(): Int {
    return flatMap { it.toList() }.max()
}