백준 17780번 : 새로운 게임 (Kotlin)

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

17780번: 새로운 게임

 

겨울에 스프링 하느라 알고리즘 오랜만에 푸는데 시간은 좀 걸렸지만 한번만에 풀려서 행복했던 문제

kotlin에서 푼 사람도 두 명 밖에 없고 해서 블로그에 풀이 해보기로했다.

 

문제 요약

NxN 의 체스판에 K(1 ~ K) 개의 말이 번호순서대로 움직인다. (4 ≤ N ≤ 12, 4 ≤ K ≤ 10)

체스판은 흰색(0) 또는 빨간색(1) 또는 파란색(2) 으로 색칠되어 있다.

말은 상하좌우 움직일 수 있고 같은 칸의 말들은 서로 업을 수 있으며 맨 아래 말만 움직일 수 있다.

 

이동하려는 칸이

• 흰색인 경우

 -> 그 칸으로 이동한다.

• 빨간색인 경우

 -> 움직이려는 말(들)을 거꾸로 뒤집어 해당 칸으로 옮긴다.

• 파란색인 경우

 -> 해당 말의 이동 방향을 반대로 하고 한 칸 이동한다. 이 때 이동하려는 칸이 파란색인 경우는 이동하지 않고 방향만 반대로 바꾼다.

• 벽인 경우

 -> 파란색과 같은 방식으로 이동

 

이동하려는 칸에 이미 말이 있는 경우 가장 위에 말(들)을 올려놓는다.

 

말이 4개 이상 쌓이는 순간 게임이 종료된다.

게임이 종료되는 턴의 번호를 출력한다.

(단 게임이 종료되지 않거나 그 값이 1000보다 큰 경우에는 -1을 출력한다.)

같은 칸에 말이 두 개 이상 있는 경우도 입력으로 주어지지 않는다.

풀이

체스판 한변크기 N,

말 갯수 K,

체스판의 색 나타내는 arr,

해당 체스판의 말 배치를 나타내는 exists,

방향 번호에 따른 이동량 dx, dy,

현재 말들의 위치 locX, locY,

현재 말들의 방향 dir,

현재 말이 제일 아래에 있는지 여부 isBottom,

움직이지 않아 연산하지 않아도 될 때 사용하는 continueFlag, 

말이 4개 이상 쌓이는지 기록하는 level

을 전역변수로 선언하고 main에서 초기화한다.

 

매 턴마다 executeTurn을 실행하고 말이 4개 이상 겹치면 빠져나온다.

종료되지 않는 경우는 1000턴을 넘을테니 turn이 1000이 넘어가면 반복문을 빠져나오는 것으로 한다.

 

기본적으로 제일 아래에 있는 말들만 움직이게 설정하였다.

가장 아래에 있는 말들은 위치값이 정확히 갱신되도록 하고 쌓여있는 말들은 현재 위치를 갱신하지 않았다.(필요 시 update)

 

맵 밖을 벗어나는 경우와 파란색 타일로 이동하는 경우는 방향을 바꾸어서 다시 이동해야 하니 먼저 if문으로 넣어준다.

이때 방향을 바꾸는 changeDir 함수를 거치는데 1과 2, 3과 4를 바꾸어야하니까

1, 2인 경우 3 - 현재 방향번호

3, 4인 경우 7 - 현재 방향 번호

로 방향을 바꾸기로 했다.

현재 방향에 3을 나눈 값으로 1, 2 ->0으로  3, 4 ->1로 바꾼 다음 그 값에 *4+3을 해줘서 1, 2로 3을, 3, 4로 7을 만들어서  현재 방향 값을 뺀 값을 새로운 방향값으로 리턴해주는 함수를 만들었다.

 

흰색으로 이동하려는 경우 현재 ArrayList값들을 모두 이동하려는 칸의 ArrayList뒤에 붙여줬다.

이미 말이 존재하는 경우는 isBottom 값을 false로 지정한다.

 

빨간색으로 이동하려는 경우 현재 ArrayList 값들의 reversed를 이동하려는 칸의 ArrayList뒤에 붙였다.

이동칸에 말이 존재하지 않는 경우는 reversed된 ArrayList의 bottom에 위치와 isBottom 을 update하고

이동칸에 말이 존재하는 경우는 움직이는 말의 isBottom값을 false로 넣는다.

 

매 이동마다 이동한 칸의 말들이 쌓인 높이가 4 이상인지 검사한다.

 

 

 

코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.StringTokenizer
import kotlin.math.max

//17780 새로운 게임

var N = 0
var K = 0
var arr = arrayOf<IntArray>()
var exists = arrayOf<Array<ArrayList<Int>>>()

var dx = arrayOf(0, 0, 0, -1, 1)
var dy = arrayOf(0, 1, -1, 0, 0)

var locX = intArrayOf()
var locY = intArrayOf()
var dir = intArrayOf()
var isBottom = booleanArrayOf()
var continueFlag = booleanArrayOf()
var level = 1


fun executeTurn(){

    for(i in 1..K){
        val nowX = locX[i]
        val nowY = locY[i]
        if(isBottom[i] && continueFlag[i]){

            var nextX = nowX + dx[dir[i]]
            var nextY = nowY + dy[dir[i]]

            //맵 벗어나는 경우 1 <->2 , 3 <-> 4
            if((nextX < 1) || (nextX > N) || (nextY < 1) || (nextY > N)){
                dir[i] = changeDir(dir[i])
                nextX = nowX + dx[dir[i]]
                nextY = nowY + dy[dir[i]]

            }

            //파란색
            if(arr[nextX][nextY] == 2){
                dir[i] = changeDir(dir[i])
                nextX = nowX + dx[dir[i]]
                nextY = nowY + dy[dir[i]]

                //진행: 파란색 or 벽
                if((nextX < 1) || (nextX > N) || (nextY < 1) || (nextY > N) || (arr[nextX][nextY] == 2)){
                    nextX = nowX
                    nextY = nowY
                    continueFlag[i] = false
                }

            }

            if(continueFlag[i]){
                //흰색
                if(arr[nextX][nextY] == 0){
                    val horses = exists[nowX][nowY]
                    val isEmpty = exists[nextX][nextY].isEmpty()
                    exists[nextX][nextY].addAll(horses)

                    if(!isEmpty){
                        isBottom[i] = false
                    }

                    exists[nowX][nowY].clear()
                    locX[i] = nextX
                    locY[i] = nextY
                }

                //빨간색
                if(arr[nextX][nextY] == 1){

                    var horses = ArrayList<Int>(exists[nowX][nowY].reversed())
                    val isEmpty = exists[nextX][nextY].isEmpty()
                    exists[nextX][nextY].addAll(horses)
                    val bottom = horses[0]
                    isBottom[i] = false

                    if(isEmpty){
                        isBottom[bottom] = true
                        locX[bottom] = nextX
                        locY[bottom] = nextY
                    }
                    exists[nowX][nowY].clear()
                }
            }
            level = max(level, exists[nextX][nextY].size)

        }
    }
}

fun changeDir(nowDir: Int): Int{
    val base: Int = nowDir / 3
    return  4 * base + 3 - nowDir
}


fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    var tok = StringTokenizer(readLine())
    N = tok.nextToken().toInt()
    K = tok.nextToken().toInt()

    arr = Array(N + 1){IntArray(N + 1){0} }
    exists = Array(N + 1){Array(N + 1){ArrayList<Int>()} }
    locX = IntArray(K + 1)
    locY = IntArray(K + 1)
    dir = IntArray(K + 1)
    isBottom = BooleanArray(K + 1){true}
    continueFlag = BooleanArray(K + 1){true}

    for(i in 1..N){
        tok = StringTokenizer(readLine())
        for(j in 1..N){
            arr[i][j] = tok.nextToken().toInt()
        }
    }

    for(i in 1..K){
        tok = StringTokenizer(readLine())
        locX[i] = tok.nextToken().toInt()
        locY[i] = tok.nextToken().toInt()
        dir[i] = tok.nextToken().toInt()
        exists[locX[i]][locY[i]].add(i)
    }

    var turn = 0

    while(turn < 1000){
        ++turn
        executeTurn()


        if(level >= 4){
            break
        }
    }

    if(level >= 4){
        print("$turn\n")
    }else{
        print("-1\n")
    }

}