본문 바로가기
Algorithm/문제 풀이

[알고리즘] 2048 (Easy) (백준 12100번)

by Sky Titan 2020. 10. 5.
728x90
 

12100번: 2048 (Easy)

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

www.acmicpc.net

 삼성 기출 문제인데 정말 삼성스러운 문제라고 할 수 있다. 시뮬레이션 + 브루트 포스 문제다. 이전의 다른 삼성 기출 문제들과 마찬가지로 맵에서 여러 물체를 동시에 움직이는 것을 구현해야한다.

 

Solution

1. 전역 변수

var N = 0
lateinit var map : Array<Array<Int>>
var max = 0

val UP = 0
val DOWN = 1
val LEFT = 2
val RIGHT = 3

 상하좌우를 나타내는 상수들과 그 외의 기본 변수들이다.

 

2. 백트랙킹

fun backTracking(depth : Int, dir_list : IntArray)
{
    if(depth == 5)
    {
        var other_map : Array<Array<Int>> = Array(N, { Array(N, {0}) })
        map.forEachIndexed { index, ints -> other_map[index] = ints.clone() }

        for(i in 0 until 5)
        {
            var dir = dir_list[i]
            tiltMap(dir, other_map)
        }
        checkMax(other_map)
    }
    else
    {
        for(dir in UP..RIGHT)
        {
            dir_list[depth] = dir
            backTracking(depth + 1, dir_list)
        }
    }
}

 브루트 포스 문제인만큼 백트랙킹으로 만들 수 있는 모든 방향 조합을 만들었다. 순서를 지킴과 동시에 방향은 중복이 가능하므로 중복 순열에 해당한다. 4 ^ 5의 경우의 수가 생긴다.

 

3. tiltMap 보드 기울이기

fun tiltMap(dir : Int, map : Array<Array<Int>>)
{
    //상
    if(dir == UP)
    {
        for(j in 0 until N)
        {
            removeBlankInLine(dir, 0, j, map)

            for(i in 0 until N - 1)
            {
                if(map[i + 1][j] > 0)
                {
                    if(map[i][j] == map[i + 1][j])
                    {
                        map[i][j] *= 2
                        map[i + 1][j] = 0
                    }
                }
            }

            removeBlankInLine(dir, 0, j, map)
        }
    }
    else if(dir == DOWN)
    {
        for(j in 0 until N)
        {
            removeBlankInLine(dir, 0, j, map)

            for(i in N - 1 downTo 1)
            {
                if(map[i - 1][j] > 0)
                {
                    if(map[i][j] == map[i - 1][j])
                    {
                        map[i][j] *= 2
                        map[i - 1][j] = 0
                    }
                }
            }

            removeBlankInLine(dir, 0, j, map)
        }
    }
    else if(dir == LEFT)
    {
        for(i in 0 until N)
        {
            removeBlankInLine(dir, i, 0, map)

            for(j in 0 until N - 1)
            {
                if(map[i][j + 1] > 0)
                {
                    if(map[i][j] == map[i][j + 1])
                    {
                        map[i][j] *= 2
                        map[i][j + 1] = 0
                    }
                }
            }

            removeBlankInLine(dir, i, 0, map)
        }
    }
    else
    {
        for(i in 0 until N)
        {
            removeBlankInLine(dir, i, 0, map)

            for(j in N - 1 downTo 1)
            {
                if(map[i][j - 1] > 0)
                {
                    if(map[i][j] == map[i][j - 1])
                    {
                        map[i][j] *= 2
                        map[i][j - 1] = 0
                    }
                }
            }

            removeBlankInLine(dir, i, 0, map)
        }
    }
}

 정해진 방향 순서에 따라 맵을 기울이는 함수로 이 문제의 제일 까다로운 부분이다.

  1. 움직이는 방향 쪽으로 블록들을 한 번 밀착시킨다. (removeBlankInLine)
  2. 합쳐지는 블록들을 처리한다.
  3. 블록들이 합쳐진 이후 생긴 빈칸들을 없애기 위해 밀착시킨다. (removeBlankInLine)

 

4. removeBlankInLine

fun removeBlankInLine(dir: Int, i : Int, j : Int, map: Array<Array<Int>>)
{
    if(dir == UP)
    {
        for(i in 0 until N - 1)
        {
            if(map[i][j] == 0)
                moveBlockToHere(dir, i, j, map)
        }
    }
    else if(dir == DOWN)
    {
        for(i in N - 1 downTo 1)
        {
            if(map[i][j] == 0)
                moveBlockToHere(dir, i, j, map)
        }
    }
    else if(dir == LEFT)
    {
        for(j in 0 until N - 1)
        {
            if(map[i][j] == 0)
                moveBlockToHere(dir, i, j, map)
        }
    }
    else
    {
        for(j in N - 1 downTo 1)
        {
            if(map[i][j] == 0)
                moveBlockToHere(dir, i, j, map)
        }
    }
}

 해당 방향 쪽으로 블록들을 이동시켜 밀착시키는 함수다.

  1. 해당 행 혹은 열을 탐색하면서 빈 칸이 있으면 가장 가까운 블록을 옮겨 온다. (moveBlockToHere)

 

5. moveBlockToHere

fun moveBlockToHere(dir : Int, x : Int, y : Int, map : Array<Array<Int>>)
{
    if(dir == UP)
    {
        for(i in x + 1 until N)
        {
            if(map[i][y] > 0)
            {
                map[x][y] = map[i][y];
                map[i][y] = 0
                break
            }
        }
    }
    else if(dir == DOWN)
    {
        for(i in x - 1 downTo 0)
        {
            if(map[i][y] > 0)
            {
                map[x][y] = map[i][y];
                map[i][y] = 0
                break
            }
        }
    }
    else if(dir == LEFT)
    {
        for(j in y + 1 until N)
        {
            if(map[x][j] > 0)
            {
                map[x][y] = map[x][j];
                map[x][j] = 0
                break
            }
        }
    }
    else
    {
        for(j in y - 1 downTo 0)
        {
            if(map[x][j] > 0)
            {
                map[x][y] = map[x][j];
                map[x][j] = 0
                break
            }
        }
    }
}

 빈 칸인 [x, y]로부터 가장 가까이 있는 블록을 [x, y]로 옮겨온다.

  1. 해당 행 혹은 열을 순회한다.
  2. 블록을 만나면 (map[x][j] > 0) 블록은 [x, y]로 옮기고 현재 칸은 0으로 만든다.(빈 칸으로 만듬)

 

6. checkMax

fun checkMax(map : Array<Array<Int>>)
{
    map.forEach { it.forEach { max = max(max, it) }  }
}

 맵에서 가장 큰 값을 찾는 함수다.

 

전체 코드

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.*
import kotlin.math.max

var br = BufferedReader(InputStreamReader(System.`in`))
var bw = BufferedWriter(OutputStreamWriter(System.out))

var N = 0
lateinit var map : Array<Array<Int>>
var max = 0

val UP = 0
val DOWN = 1
val LEFT = 2
val RIGHT = 3

fun solution() {

    N = br.readLine().toInt()
    map = Array(N, {Array(N, {0})})

    map.forEach{
        var strtok = StringTokenizer(br.readLine())
        it.forEachIndexed{j, v -> it[j] = strtok.nextToken().toInt() }
    }


    backTracking(0, IntArray(5))
    bw.write(max.toString())
}

fun backTracking(depth : Int, dir_list : IntArray)
{
    if(depth == 5)
    {
        var other_map : Array<Array<Int>> = Array(N, { Array(N, {0}) })
        map.forEachIndexed { index, ints -> other_map[index] = ints.clone() }

        for(i in 0 until 5)
        {
            var dir = dir_list[i]
            tiltMap(dir, other_map)
        }
        checkMax(other_map)
    }
    else
    {
        for(dir in UP..RIGHT)
        {
            dir_list[depth] = dir
            backTracking(depth + 1, dir_list)
        }
    }
}

fun tiltMap(dir : Int, map : Array<Array<Int>>)
{
    //상
    if(dir == UP)
    {
        for(j in 0 until N)
        {
            removeBlankInLine(dir, 0, j, map)

            for(i in 0 until N - 1)
            {
                if(map[i + 1][j] > 0)
                {
                    if(map[i][j] == map[i + 1][j])
                    {
                        map[i][j] *= 2
                        map[i + 1][j] = 0
                    }
                }
            }

            removeBlankInLine(dir, 0, j, map)
        }
    }
    else if(dir == DOWN)
    {
        for(j in 0 until N)
        {
            removeBlankInLine(dir, 0, j, map)

            for(i in N - 1 downTo 1)
            {
                if(map[i - 1][j] > 0)
                {
                    if(map[i][j] == map[i - 1][j])
                    {
                        map[i][j] *= 2
                        map[i - 1][j] = 0
                    }
                }
            }

            removeBlankInLine(dir, 0, j, map)
        }
    }
    else if(dir == LEFT)
    {
        for(i in 0 until N)
        {
            removeBlankInLine(dir, i, 0, map)

            for(j in 0 until N - 1)
            {
                if(map[i][j + 1] > 0)
                {
                    if(map[i][j] == map[i][j + 1])
                    {
                        map[i][j] *= 2
                        map[i][j + 1] = 0
                    }
                }
            }

            removeBlankInLine(dir, i, 0, map)
        }
    }
    else
    {
        for(i in 0 until N)
        {
            removeBlankInLine(dir, i, 0, map)

            for(j in N - 1 downTo 1)
            {
                if(map[i][j - 1] > 0)
                {
                    if(map[i][j] == map[i][j - 1])
                    {
                        map[i][j] *= 2
                        map[i][j - 1] = 0
                    }
                }
            }

            removeBlankInLine(dir, i, 0, map)
        }
    }
}

fun removeBlankInLine(dir: Int, i : Int, j : Int, map: Array<Array<Int>>)
{
    if(dir == UP)
    {
        for(i in 0 until N - 1)
        {
            if(map[i][j] == 0)
                moveBlockToHere(dir, i, j, map)
        }
    }
    else if(dir == DOWN)
    {
        for(i in N - 1 downTo 1)
        {
            if(map[i][j] == 0)
                moveBlockToHere(dir, i, j, map)
        }
    }
    else if(dir == LEFT)
    {
        for(j in 0 until N - 1)
        {
            if(map[i][j] == 0)
                moveBlockToHere(dir, i, j, map)
        }
    }
    else
    {
        for(j in N - 1 downTo 1)
        {
            if(map[i][j] == 0)
                moveBlockToHere(dir, i, j, map)
        }
    }
}


fun moveBlockToHere(dir : Int, x : Int, y : Int, map : Array<Array<Int>>)
{
    if(dir == UP)
    {
        for(i in x + 1 until N)
        {
            if(map[i][y] > 0)
            {
                map[x][y] = map[i][y];
                map[i][y] = 0
                break
            }
        }
    }
    else if(dir == DOWN)
    {
        for(i in x - 1 downTo 0)
        {
            if(map[i][y] > 0)
            {
                map[x][y] = map[i][y];
                map[i][y] = 0
                break
            }
        }
    }
    else if(dir == LEFT)
    {
        for(j in y + 1 until N)
        {
            if(map[x][j] > 0)
            {
                map[x][y] = map[x][j];
                map[x][j] = 0
                break
            }
        }
    }
    else
    {
        for(j in y - 1 downTo 0)
        {
            if(map[x][j] > 0)
            {
                map[x][y] = map[x][j];
                map[x][j] = 0
                break
            }
        }
    }
}

fun checkMax(map : Array<Array<Int>>)
{
    map.forEach { it.forEach { max = max(max, it) }  }
}


fun main() {
    solution()
    br.close()
    bw.close()
}
728x90
저작자표시 비영리

'Algorithm > 문제 풀이' 카테고리의 다른 글

[알고리즘] DSLR (백준 9019번)  (0) 2020.10.05
[알고리즘] 뱀 (백준 3190번)  (0) 2020.10.05
[알고리즘] ACM Craft (백준 1005번)  (0) 2020.10.05
[알고리즘] 외판원 순회 2 (백준 10971번)  (0) 2020.10.04
[알고리즘] 가르침 (백준 1062번)  (0) 2020.10.03

관련글

댓글

티스토리툴바