백준 12094 2048 (Hard) Kotlin (시뮬레이션, 백트래킹)

문제 출처 : https://www.acmicpc.net/problem/12094

12094번: 2048 (Hard)

문제

2048 게임은 4×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다. 이 링크를 누르면 게임을 해볼 수 있다.

이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다)

<그림 1>의 경우에서 위로 블록을 이동시키면 <그림 2>의 상태가 된다. 여기서, 왼쪽으로 블록을 이동시키면 <그림 3>의 상태가 된다.

<그림 4>의 상태에서 블록을 오른쪽으로 이동시키면 <그림 5>가 되고, 여기서 다시 위로 블록을 이동시키면 <그림 6>이 된다. 여기서 오른쪽으로 블록을 이동시켜 <그림 7>을 만들 수 있다.

<그림 8>의 상태에서 왼쪽으로 블록을 옮기면 어떻게 될까? 2가 충돌하기 때문에, 4로 합쳐지게 되고 <그림 9>의 상태가 된다.

<그림 10>에서 위로 블록을 이동시키면 <그림 11>의 상태가 된다. 

<그림 12>의 경우에 위로 블록을 이동시키면 <그림 13>의 상태가 되는데, 그 이유는 한 번의 이동에서 이미 합쳐진 블록은 또 합쳐질 수 없기 때문이다.

마지막으로, 똑같은 수가 세 개가 있는 경우에는 이동하려고 하는 쪽의 칸이 먼저 합쳐진다. 예를 들어, 위로 이동시키는 경우에는 위쪽에 있는 블록이 먼저 합쳐지게 된다. <그림 14>의 경우에 위로 이동하면 <그림 15>를 만든다.

이 문제에서 다루는 2048 게임은 보드의 크기가 N×N 이다. 보드의 크기와 보드판의 블록 상태가 주어졌을 때, 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.

출력

최대 10번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.

풀이

2021.12.23 - [알고리즘 문제 풀이/백준] - 백준 12100 2048(Easy) Kotlin (시뮬레이션)

 

Easy를 필히 풀어보고 오는 것을 추천한다.

Easy 문제를 풀고 풀이의 검증을 받지 않은채 Hard 문제를 푼다면 디버깅 지옥에 빠질 것이다.

Easy 문제랑 다른 점은 dfs의 뎁스 뿐이다. Easy문제에선 최대 5번 이동했으나 이번엔 최대 10번이다.

2048 문제에서 뎁스가 5 늘어나는 것은 가짓수가 엄청나게 많아지기 때문에, 고작 5번의 이동이 추가되었으나

적절한 백트래킹(가지치기)을 이용하지 않으면 시간 초과를 면할 수 없다.

 

Easy문제의 로직은 조금만 수정하면 그대로 쓸 수 있다.

우선 두 가지 백트래킹 조건이 추가된다.

 

1. 이동한 후의 그래프가 이동 전 그래프와 같은 모양이라면 해당 dfs는 더 이상 깊이 내려가지 않는다.

2. dfs는 깊이 우선 탐색이다. 따라서 이전 탐색에서 구한 최댓값이 있을 것이고 이를 A라 하면, 현재 그래프가 2번 이동했을 때 나머지 8번을 움직여도 A보다 높은 결과가 나올 수 없다면 해당 dfs는 더 이상 깊이 내려가지 않는다.

 

1번 조건은 쉽다.

그냥 이동 전 그래프와 이동 후 그래프를 완전 탐색으로 비교하면 된다. 최대 이동 횟수가 정해져 있는 이 문제에선 이는 쓸데없는 움직임이다. 쓸데없는 움직임에 횟수를 낭비하면 이의 결과는 최댓값을 갱신할 수 없다.

 

2번 조건은 현재 그래프가 남은 이동 횟수만큼 다 이동해도 최댓값보다 작을지 클지 어떻게 알아? 라고 생각할 텐데.

현재까지 이동한 횟수를 cnt라 하자. 기대할 수 있는 최댓값은 현재 그래프의 최댓값이 10-cnt만큼 합쳐지는 경우이다.

즉 현재 그래프의 최댓값을 curMax라 할 때, 기대되는 최댓값 expectedMax = curMax << (10-cnt)이다.

expectedMax가 이전 탐색에서 구한 최댓값보다 크지 않다면 이 dfs는 더 이상 탐색할 필요가 없는 것이다. 

 

혹시라도 이전 Easy 문제를 내 풀이를 참고했다면 좀 바꿔야 할 부분이 있다.

이전엔 가지치기를 하지 않았기 때문에 모든 dfs가 뎁스 5까지 도달했다.

따라서 뎁스 5일 때만 최댓값을 갱신하면 됐는데, 이 문제는 가지치기를 해야 하기 때문에 뎁스 10까지 도달하지 못하는 경우가 발생한다. 따라서 모든 경우에 최댓값을 갱신해줘야 한다.

 

본인은 25번의 제출만에 통과했는데 원래 코드에서 그래프의 최댓값 추출, 다음 그래프와 현재 그래프가 다른지 여부 추출을 쏙 집어넣었더니 기존 코드에선 break, return 때문에 값이 제대로 추출되지 않았어서 맞왜틀만 15번 한 거 같다.

날로 먹으려 하지 말자..! 

 

코드

val br = System.`in`.bufferedReader()
var answer =0
var maxVal = 0
fun check(n : Int, graph : Array<IntArray>, temp : Array<IntArray>) : Boolean{
    var isSame = true
    for(i in 0 until n){
        for(j in 0 until n){
            maxVal = maxVal.coerceAtLeast(temp[i][j])
            if(graph[i][j]!=temp[i][j])
                isSame= false
        }
    }
    return isSame
}

fun move(i : Int, n : Int, temp : Array<IntArray>){
    when{
        //상
        i==0 ->{
            for(c in 0 until n){
                for(r in 0 until n-1){
                    //현재 칸에 블럭이 있는 경우 합치기
                    if(temp[r][c]!=0){
                        var idx=r+1
                        //아래측의 최초 블럭
                        while(idx<n && temp[idx][c]==0){
                            idx++
                        }
                        //아래측에 블럭이 없는 경우
                        if(idx==n) break
                        //숫자가 같은 경우
                        if(temp[r][c]==temp[idx][c]){
                            temp[r][c]*=2.also{temp[idx][c]=0}
                        }
                        //숫자가 다른 경우
                        else{
                            temp[r+1][c]=temp[idx][c].also{temp[idx][c]=0}
                        }
                    }
                }
                for(r in 0 until n){
                    //이동한 그래프의 최댓값 찾기
                    maxVal=maxVal.coerceAtLeast(temp[r][c])
                    //현재 칸에 블럭이 없는 경우 swap
                    if(temp[r][c]==0){
                        var idx=r+1
                        //아래측의 최초 블럭
                        while(idx<n &&temp[idx][c]==0){
                            idx++
                        }
                        //아래측에 블럭이 없는 경우
                        if(idx==n) break
                        //아래측에 블럭이 있는 경우 swap
                        temp[r][c]=temp[idx][c].also{temp[idx][c]=0}
                    }
                }
            }
        }
        //하
        i==1 ->{
            for(c in 0 until n){
                for(r in n-1 downTo 1){
                    //현재 칸에 블럭이 있는 경우 합치기
                    if(temp[r][c]!=0){
                        var idx=r-1
                        //위측의 최초 블럭
                        while(idx>=0 && temp[idx][c]==0){
                            idx--
                        }
                        //위측에 블럭이 없는 경우
                        if(idx<0) break
                        //숫자가 같은 경우
                        if(temp[r][c]==temp[idx][c]){
                            temp[r][c]*=2.also{temp[idx][c]=0}
                        }
                        //숫자가 다른 경우
                        else{
                            temp[r-1][c]=temp[idx][c].also{temp[idx][c]=0}
                        }
                    }
                }
                for(r in n-1 downTo 0){
                    //이동한 그래프의 최댓값 찾기
                    maxVal=maxVal.coerceAtLeast(temp[r][c])
                    //현재 칸에 블럭이 없는 경우 swap
                    if(temp[r][c]==0){
                        var idx=r-1
                        //위측의 최초 블럭
                        while(idx>=0 && temp[idx][c]==0){
                            idx--
                        }
                        //위측에 블럭이 없는 경우
                        if(idx<0) break
                        //위측에 블럭이 있는 경우 swap
                        temp[r][c]=temp[idx][c].also{temp[idx][c]=0}
                    }
                }
            }
        }
        //좌
        i==2 ->{
            for(r in 0 until n){
                for(c in 0 until n-1){
                    //현재 칸에 블럭이 있는 경우 합치기
                    if(temp[r][c]!=0){
                        var idx=c+1
                        //우측의 최초 블럭
                        while(idx<n && temp[r][idx]==0){
                            idx++
                        }
                        //우측에 블럭이 없는 경우
                        if(idx==n) break
                        //숫자가 같은 경우
                        if(temp[r][c]==temp[r][idx]){
                            temp[r][c]*=2.also{temp[r][idx]=0}
                        }
                        //숫자가 다른 경우
                        else{
                            temp[r][c+1]=temp[r][idx].also{temp[r][idx]=0}
                        }
                    }
                }
                for(c in 0 until n){
                    //이동한 그래프의 최댓값 찾기
                    maxVal=maxVal.coerceAtLeast(temp[r][c])
                    //현재 칸에 블럭이 없는 경우 swap
                    if(temp[r][c]==0){
                        var idx=c+1
                        //우측의 최초 블럭
                        while(idx<n && temp[r][idx]==0){
                            idx++
                        }
                        //우측에 블럭이 없는 경우
                        if(idx==n) break
                        //우측에 블럭이 있는 경우 swap
                        temp[r][c]=temp[r][idx].also{temp[r][idx]=0}
                    }
                }
            }
        }
        //우
        i==3 ->{
            for(r in 0 until n){
                for(c in n-1 downTo 1){
                    //현재 칸에 블럭이 있는 경우 합치기
                    if(temp[r][c]!=0){
                        var idx=c-1
                        //좌측의 최초 블럭
                        while(idx>=0 && temp[r][idx]==0){
                            idx--
                        }
                        //좌측에 블럭이 없는 경우
                        if(idx<0) break
                        //숫자가 같은 경우
                        if(temp[r][c]==temp[r][idx]){
                            temp[r][c]*=2.also{temp[r][idx]=0}
                        }
                        //숫자가 다른 경우
                        else{
                            temp[r][c-1]=temp[r][idx].also{temp[r][idx]=0}
                        }
                    }
                }
                for(c in n-1 downTo 0){
                    //이동한 그래프의 최댓값 찾기
                    maxVal=maxVal.coerceAtLeast(temp[r][c])
                    //현재 칸에 블럭이 없는 경우 swap
                    if(temp[r][c]==0){
                        var idx=c-1
                        //좌측의 최초 블럭
                        while(idx>=0 && temp[r][idx]==0){
                            idx--
                        }
                        //좌측에 블럭이 없는 경우
                        if(idx<0) break
                        //좌측에 블럭이 있는 경우 swap
                        temp[r][c]=temp[r][idx].also{temp[r][idx]=0}
                    }
                }
            }
        }
    }

}

fun dfs(cnt : Int, n : Int, graph : Array<IntArray>){

    if(cnt==10){
        return
    }

    for(i in 0 until 4){
        //copy
        val temp =  Array(n) { IntArray(n) }
        for(r in 0 until n){
            for(c in 0 until n){
                temp[r][c]=graph[r][c]
            }
        }
        maxVal=0
        //move
        move(i,n,temp)
        //check 함수에서 maxVal, 이전 그래프와 같은지 여부를 추출
        val isSame = check(n,graph,temp)
        //정답 갱신
        answer=answer.coerceAtLeast(maxVal)

        //이동했을 때 차이가 없다면 스킵
        if(isSame) continue

        //다음 그래프의 최댓값에서 남은 이동 횟수를 계산한 최댓값이 절대 최댓값이 나올 수 없으면 스킵
        if(maxVal shl (9-cnt) <=answer) continue
        dfs(cnt + 1, n, temp)
    }
}

fun main() =with(System.out.bufferedWriter()){

    val n = br.readLine().toInt()

    val graph= Array(n){br.readLine().split(' ').map{it.toInt()}.toIntArray()}

    dfs(0,n,graph)
    write("$answer")
    close()
}