[알고리즘] 뱀 (백준 3190번)

3190번: 뱀

 삼성 기출의 시뮬레이션 문제다. 지도 상에서 뱀이 움직이는 것을 구현해야 하는 문제다.

 

Solution

1. 전역 변수

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

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

var orders : Queue<Order> = LinkedList()
var snake = ArrayList<Position>()

 기본 변수들과 상하좌우를 나타내는 상수, 명령들을 보관하고 있는 큐와 뱀을 표현하는 ArrayList를 하나 뒀다. 뱀의 머리는 snake.first가 될 것이고 꼬리는 snake.last가 될 것이다.

 

2. solution

fun solution() {

    N = br.readLine().toInt()
    K = br.readLine().toInt()

    map = Array(N + 1, { Array(N + 1, {0}) })

    for(i in 0 until K)
    {
        var strtok = StringTokenizer(br.readLine())
        var x = strtok.nextToken().toInt()
        var y = strtok.nextToken().toInt()

        map[x][y] = 1
    }

    //머리부분분
   map[1][1] = 2

    snake.add(Position(1, 1))

    var L = br.readLine().toInt()

    for(i in 0 until L)
    {
        var strtok = StringTokenizer(br.readLine())
        var time = strtok.nextToken().toInt()
        var dir = strtok.nextToken()[0]

        orders.offer(Order(time, dir))
    }

    bw.write(simulation().toString())
}

 기본 입력을 받고 사과들의 위치는 맵에서 1로 표시를 했고 뱀이 있는 곳은 2로 표시를 한다.

 

3. simulation

fun simulation() :Int
{
    var current_time = 0
    var dir = RIGHT

    while(true)
    {
        if(!orders.isEmpty())
        {
            var order = orders.peek()

            //방향 회전 시간
            if(order.time == current_time)
            {
                orders.poll()
                dir = turnDirection(dir, order.dir)
            }
        }

        current_time++

        //뱀움직임
        if(!moveSnake(dir))
            return current_time
    }
}

 시뮬레이션을 진행하는 곳이다. dir은 현재 뱀이 움직이고 있는 방향이다.

1. 무한 루프를 돈다.
   1. 현재 orders의 front에 있는 명령 실행 시간이  현재 시간과 일치하는지 확인한다. (order.time == current_time)
      1. 일치한다면 명령에서 말한 방향으로 뱀 머리 방향을 회전시켜 dir을 새로 갱신한다. (turnDirection)
   2. 현재 시간을 증가시키고 뱀을 움직인다.(moveSnake)
      1. 만약 뱀이 벽에 부딪히거나 자기 몸에 부딪혀서 게임 종료 조건이 성립되면 false를 반환하므로 이 때 current_time을 반환하고 함수를 종료한다.

 

4. turnDirection

fun turnDirection(current_Dir : Int, changed_Dir : Char) : Int
{
    //왼쪽 90도
    if(changed_Dir == 'L')
    {
        when(current_Dir)
        {
            UP -> return LEFT
            DOWN -> return RIGHT
            LEFT -> return DOWN
            else -> return UP
        }

    }
    //오른쪽 90도
    else
    {
        when(current_Dir)
        {
            UP -> return RIGHT
            DOWN -> return LEFT
            LEFT -> return UP
            else -> return DOWN
        }
    }
}

 뱀의 현재 방향을 changed_Dir에 맞춰서 회전시킨다.

 

5. moveSnake

fun moveSnake(dir : Int) : Boolean
{
    var head = snake.first()
    var next_x = head.x
    var next_y = head.y

    when(dir)
    {
        UP -> {
            next_x --
        }

        DOWN -> {
            next_x ++
        }

        LEFT -> {
            next_y --
        }

        RIGHT -> {
            next_y ++
        }
    }

    //벽 안에 정상적으로 이동
    if(1 <= next_x && next_x <= N && 1 <= next_y && next_y <= N)
    {
        //자기 몸과 부딪힘
        if(map[next_x][next_y] == 2)
            return false
        else
        {
            //사과 놓여져 있으면 꼬리 증가
            if(map[next_x][next_y] == 1)
                snake.add(Position(0 ,0))
            //빈칸이면 꼬리 수축
            else
            {
                var tail = snake.last()
                map[tail.x][tail.y] = 0
            }

            //몸 이동
            for(i in snake.size - 1 downTo 1)
            {
                snake[i].x = snake[i - 1].x
                snake[i].y = snake[i - 1].y
            }

            //머리 이동
            head.x = next_x
            head.y = next_y
            map[head.x][head.y] = 2

        }
    }
    //벽에 부딪힘
    else
        return false

    return true
}

 뱀을 현재 방향 쪽으로 움직인다.

1. 뱀 머리의 다음 위치를 next_x, next_y에 저장한다.
   1. 만약 맵을 벗어낫다면 false를 반환한다.
   2. 다음 위치의 숫자가 2이면 자기 몸과 부딪힌 것이므로 false를 반환한다.
   3. 다음 위치의 숫자가 1이면 사과를 먹은 것이므로 snake에 요소를 추가해 몸 길이를 늘린다.
      1. 빈 칸이면 원래 꼬리가 있던 칸의 숫자를 0으로 만들어서 꼬리를 이동시킨다.
   4. 몸을 이동시킨다.
   5. 마지막으로 머리를 이동시키고 새로운 머리 위치에 2를 표시한다.
2. 성공적으로 움직였으면 true를 반환한다.

 

전체 코드

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.*
import kotlin.collections.ArrayList

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

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

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

var orders : Queue<Order> = LinkedList()
var snake = ArrayList<Position>()

fun solution() {

    N = br.readLine().toInt()
    K = br.readLine().toInt()

    map = Array(N + 1, { Array(N + 1, {0}) })

    for(i in 0 until K)
    {
        var strtok = StringTokenizer(br.readLine())
        var x = strtok.nextToken().toInt()
        var y = strtok.nextToken().toInt()

        map[x][y] = 1
    }

    //머리부분분
   map[1][1] = 2

    snake.add(Position(1, 1))

    var L = br.readLine().toInt()

    for(i in 0 until L)
    {
        var strtok = StringTokenizer(br.readLine())
        var time = strtok.nextToken().toInt()
        var dir = strtok.nextToken()[0]

        orders.offer(Order(time, dir))
    }

    bw.write(simulation().toString())
}

fun simulation() :Int
{
    var current_time = 0
    var dir = RIGHT

    while(true)
    {
        if(!orders.isEmpty())
        {
            var order = orders.peek()

            //방향 회전 시간
            if(order.time == current_time)
            {
                orders.poll()
                dir = turnDirection(dir, order.dir)
            }
        }

        current_time++

        //뱀움직임
        if(!moveSnake(dir))
            return current_time
    }
}

fun turnDirection(current_Dir : Int, changed_Dir : Char) : Int
{
    //왼쪽 90도
    if(changed_Dir == 'L')
    {
        when(current_Dir)
        {
            UP -> return LEFT
            DOWN -> return RIGHT
            LEFT -> return DOWN
            else -> return UP
        }

    }
    //오른쪽 90도
    else
    {
        when(current_Dir)
        {
            UP -> return RIGHT
            DOWN -> return LEFT
            LEFT -> return UP
            else -> return DOWN
        }
    }
}

fun moveSnake(dir : Int) : Boolean
{
    var head = snake.first()
    var next_x = head.x
    var next_y = head.y

    when(dir)
    {
        UP -> {
            next_x --
        }

        DOWN -> {
            next_x ++
        }

        LEFT -> {
            next_y --
        }

        RIGHT -> {
            next_y ++
        }
    }

    //벽 안에 정상적으로 이동
    if(1 <= next_x && next_x <= N && 1 <= next_y && next_y <= N)
    {
        //자기 몸과 부딪힘
        if(map[next_x][next_y] == 2)
            return false
        else
        {
            //사과 놓여져 있으면 꼬리 증가
            if(map[next_x][next_y] == 1)
                snake.add(Position(0 ,0))
            //빈칸이면 꼬리 수축
            else
            {
                var tail = snake.last()
                map[tail.x][tail.y] = 0
            }

            //몸 이동
            for(i in snake.size - 1 downTo 1)
            {
                snake[i].x = snake[i - 1].x
                snake[i].y = snake[i - 1].y
            }

            //머리 이동
            head.x = next_x
            head.y = next_y
            map[head.x][head.y] = 2

        }
    }
    //벽에 부딪힘
    else
        return false

    return true
}


data class Order(var time : Int, var dir : Char)
data class Position(var x : Int, var y : Int)


fun main() {
    solution()
    br.close()
    bw.close()
}