[백준 12100번] [Kotlin] 2048 (Easy)

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

12100번: 2048 (Easy)

 

난이도 : 골드 2
태그 : 구현, 브루트포스, 백트래킹, 시뮬레이션

 

 

설명

2048의 게임을 바탕으로 한 문제입니다.

예전에 꽤 재밌게 했던 게임이고, 자바 스윙을 배울때 GUI로 직접 구현했던 게임이였는데,

이렇게 보니 반갑네요.

 

2048 게임을 잘 모르시는 분이라면 꼭 아래 링크에서 한 번씩 해보시기 바랍니다.

https://play2048.co/

2048

 

 

 

접근방법

 

 

 

상하좌우 이동 시 모두 개념은 동일하나, 위로 이동 상황을 예시로 들겠습니다.

 

위로 이동할 경우, 제일 위 원소부터 하나씩 큐에 넣습니다.

 

2열을 예시로 들자면, 큐에 제일 위 원소부터 넣어 큐에 있는 원소는 [4, 4, 8, 8]이 됩니다.

 

 

큐에서 하나를 꺼냅니다. 큐에 남은 원소는 [4,8,8] 입니다.

 

행을 가르킬 포인터 역할을 할 ptr 변수를 하나 생성합니다.

위로 이동하는 경우이므로 초기값은 0 입니다.

 

만약 큐의 첫번째 원소(peek)가 방금 큐에서 꺼낸 원소와 같을 경우,

하나를 더 꺼내고 *2를 하고 ptr의 위치(현재 0)에 넣고, ptr를 1만큼 증가시킵니다.

 

하나를 더 꺼냈으니 현재 큐에 남은 원소는 [8,8] 입니다,

 

위 과정을 큐가 빌 때 까지 반복합니다.

 

 

아래, 오른쪽 왼쪽 이동도 비슷한 과정으로 구현하고,

최대 5번 이동하는 경우를 백트래킹으로 구하면 됩니다.

 

 

 

소스코드

 

import java.util.LinkedList
import java.util.Queue
import java.util.StringTokenizer
import kotlin.math.max

var n = 0
var max = 0L

fun main() {
    val br = System.`in`.bufferedReader()

    n = br.readLine().toInt()

    val arr = Array(n) { Array(n) { 0L } }

    repeat(n) { x ->
        val st = StringTokenizer(br.readLine())
        repeat(n) { y ->
            arr[x][y] = st.nextToken().toLong()
        }
    }

    // 백트래킹
    dfs(0, arr)

    println(max)
}

fun dfs(depth: Int, arr: Array<Array<Long>>) {

    // 5번 모두 이동 했을 경우 최대값 저장
    if (depth == 5) {
        repeat(n) { x ->
            repeat(n) { y ->
                max = max(max, arr[x][y])
            }
        }
        return
    }

    for (i in 0 until 4) {
        // 배열 복사
        val copyArr = Array(n) { Array(n) { 0L } }
        repeat(n) { x ->
            repeat(n) { y ->
                copyArr[x][y] = arr[x][y]
            }
        }

        when (i) {
            0 -> up(copyArr)
            1 -> down(copyArr)
            2 -> right(copyArr)
            3 -> left(copyArr)
        }

        dfs(depth + 1, copyArr)
    }
}


fun up(arr: Array<Array<Long>>) {
    for (i in 0 until n) {
        val q = LinkedList<Long>() as Queue<Long>

        for (j in 0 until n) {
            if (arr[j][i] == 0L) continue

            q.offer(arr[j][i])
            arr[j][i] = 0
        }

        var ptr = 0

        while (q.isNotEmpty()) {
            val target = q.poll()
            if (q.isNotEmpty() && target == q.peek()) {
                arr[ptr][i] = target * 2
                q.poll()
            } else {
                arr[ptr][i] = target
            }
            ptr++
        }
    }
}

fun down(arr: Array<Array<Long>>) {
    for (i in 0 until n) {
        val q = LinkedList<Long>() as Queue<Long>

        for (j in n - 1 downTo 0) {
            if (arr[j][i] == 0L) continue

            q.offer(arr[j][i])
            arr[j][i] = 0
        }

        var ptr = n - 1

        while (q.isNotEmpty()) {
            val target = q.poll()
            if (q.isNotEmpty() && target == q.peek()) {
                arr[ptr][i] = target * 2
                q.poll()
            } else {
                arr[ptr][i] = target
            }
            ptr--
        }
    }
}


fun left(arr: Array<Array<Long>>) {
    for (i in 0 until n) {
        val q = LinkedList<Long>() as Queue<Long>

        for (j in 0 until n) {
            if (arr[i][j] == 0L) continue

            q.offer(arr[i][j])
            arr[i][j] = 0L
        }

        var ptr = 0

        while (q.isNotEmpty()) {
            val target = q.poll()
            if (q.isNotEmpty() && target == q.peek()) {
                arr[i][ptr] = target * 2
                q.poll()
            } else {
                arr[i][ptr] = target
            }
            ptr++
        }
    }
}

fun right(arr: Array<Array<Long>>) {
    for (i in 0 until n) {
        val q = LinkedList<Long>() as Queue<Long>

        for (j in n - 1 downTo 0) {
            if (arr[i][j] == 0L) continue

            q.offer(arr[i][j])
            arr[i][j] = 0
        }

        var ptr = n - 1

        while (q.isNotEmpty()) {
            val target = q.poll()
            if (q.isNotEmpty() && target == q.peek()) {
                arr[i][ptr] = target * 2
                q.poll()
            } else {
                arr[i][ptr] = target
            }
            ptr--
        }
    }
}

 

 

 

 

후기

오랜만에 2048을 접해서 꽤 반가웠던 문제였습니다.

 

이 문제는 삼성 SW 기출문제로도 유명한데,

코딩테스트를 준비하시는 분들 모두 화이팅입니다.