[백준 12100] 2048 (Easy)

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

12100번: 2048 (Easy)

 

이 문제는 완전탐색으로 해결 할 수 있는 문제이다.

시간복잡도를 계산해 보면 

재귀를 5번 호출하는것 20*20*4^5 인데

4^5는 상하좌우를 움직이면서 재귀호출하고 매번 상하좌우로 움직일때 

총 블록의 갯수가 20*20이 되기 때문이다.

 

이 문제에서 고려해야할 부분은 총 2가지 인데

1. 상하좌우를 움직일때 기존의 map 에서 돌아야하기 때문에 기존 상태를 갖는 map이 필요.

2. 한번 합쳐진 블록은 중복돼서 합쳐지면 안되기 때문에 visit배열로 합쳐진 여부 체크.

이다.

 

위 부분을 고려해서 상하좌우로 배열을 밀어서 처리하면 되는데 나는

상하좌우로 배열을 움직일 때 변수하나를 이름을 잘못 입력해서 삽질을 했다.

 

내 코드는 아래와 같으며 이거보다 더 깔끔한 코드가 떠오르면 수정할 예정이다.

 

 

import java.io.BufferedReader
import java.io.InputStreamReader

var N = 0
fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val c = br.readLine().toInt()
    val map = Array(c) { Array(c) { 0 } }
    N = c
    for (i in 0..c - 1) {
        val input = br.readLine().split(" ")
        input.forEachIndexed { index, s ->
            map[i][index] = s.toInt()
        }
    }

    println(dfs(map, 5))

}

fun dfs(map: Array<Array<Int>>, count: Int): Int {
    var num = 0
    if (count == 0) {
        var maxNum = 0
        for (i in 0..N - 1) {
            for (j in 0..N - 1) {
                maxNum = Math.max(maxNum, map[i][j])
        
            }
  
        }

        return maxNum
    }

    val clonedMap = Array(N) { Array(N) { 0 } }
    val isVisit = Array(N) { Array(N) { false } }

    for (i in 0..N - 1) {
        for (j in 0..N - 1) {
            clonedMap[i][j] = map[i][j]
        }
    }

    for (c in 0..3) {
        for (i in 0..N - 1) {
            for (j in 0..N - 1) {
                map[i][j] = clonedMap[i][j]
                isVisit[i][j] = false
            }
        }
        //상
        if (c == 0) {
            for (j in 0..N - 1) {
                for (i in 1..N - 1) {
                    var pos = i
                    if (map[pos][j] != 0) {
                        while (true) {
                            if (map[pos - 1][j] == 0) {
                                map[pos - 1][j] = map[pos][j]
                                map[pos][j] = 0
                            } else if (map[pos - 1][j] == map[pos][j] && isVisit[pos - 1][j].not()) {
                                map[pos - 1][j] += map[pos][j]
                                map[pos][j] = 0
                                isVisit[pos - 1][j] = true
                                break
                            } else {
                                break
                            }
                            pos--
                            if (pos == 0) break
                        }
                    }
                }
            }

        }
        //하
        else if (c == 1) {
            for (j in 0..N - 1) {
                for (i in N - 2 downTo 0) {
                    var pos = i
                    if (map[pos][j] != 0) {
                        while (true) {
                            if (map[pos + 1][j] == 0) {
                                map[pos + 1][j] = map[pos][j]
                                map[pos][j] = 0
                            } else if (map[pos + 1][j] == map[pos][j] && isVisit[pos + 1][j].not()) {
                                map[pos + 1][j] += map[pos][j]
                                map[pos][j] = 0
                                isVisit[pos + 1][j] = true
                                break
                            } else {
                                break
                            }
                            pos++
                            if (pos == N - 1) break
                        }
                    }
                }
            }
        }
        //좌
        else if (c == 2) {
            for (i in 0..N - 1) {
                for (j in 1..N - 1) {
                    var pos = j
                    if (map[i][pos] != 0) {
                        while (true) {
                            if (map[i][pos - 1] == 0) {
                                map[i][pos - 1] = map[i][pos]
                                map[i][pos] = 0
                            } else if (map[i][pos - 1] == map[i][pos] && isVisit[i][pos - 1].not()) {
                                map[i][pos - 1] += map[i][pos]
                                map[i][pos] = 0
                                isVisit[i][pos - 1] = true
                                break
                            } else {
                                break
                            }
                            pos--
                            if (pos == 0) break
                        }
                    }
                }
            }
        }
        //우
        else if (c == 3) {
            for (i in 0..N - 1) {
                for (j in N - 2 downTo 0) {
                    var pos = j
                    if (map[i][pos] != 0) {
                        while (true) {
                            if (map[i][pos + 1] == 0) {
                                map[i][pos + 1] = map[i][pos]
                                map[i][pos] = 0
                            } else if (map[i][pos + 1] == map[i][pos] && isVisit[i][pos + 1].not()) {
                                map[i][pos + 1] += map[i][pos]
                                map[i][pos] = 0
                                isVisit[i][pos + 1] = true
                                break
                            } else {
                                break
                            }
                            pos++
                            if (pos == N - 1) break
                        }
                    }
                }
            }
        }



        num = Math.max(num, dfs(map, count - 1))
    }

    return num
}