[알고리즘] 어른 상어 (백준 19237번)

19237번: 어른 상어

 시뮬레이션으로 악명 높은 삼성 기출 문제다. 삼성은 맵 위에 물체들이 동시에 움직이는 시뮬레이션 문제를 좋아하는 것 같다. 저번에도 몇 번 삼성 익스퍼트 아카데미에서 비슷한 부류의 문제를 본 적이 있다. 각 물체들의 동작이 서로 비동기적으로 일어나는 것을 표현해줘야 하기에 생각보다 어렵다.

 

Solution

1. 전역 변수들

lateinit var map : Array<IntArray>
lateinit var sharkList : List<Shark>
lateinit var queue_smell : Array<Queue<Smell>>
lateinit var priority : Array<Array<IntArray>>
lateinit var isDead : BooleanArray
var N : Int = 0
var M : Int = 0
var K : Int = 0

 map은 말그대로 맵이고 sharkList는 상어들의 현재 위치를 가지고 있다. queue_smell은 queue 배열로, 각 상어마다 하나씩 큐를 가지고 있고 이 큐에는 각 상어가 뿌리고 다닌 냄새들의 위치 정보를 담고 있다. 상어들이 한 번 이동할 때마다 냄새들을 dequeue하여서 냄새를 지우는 것을 표현했다.

 priority는 우선순위 정보들을 담고 isDead 배열은 상어들이 살아있는지 여부를 판단한다.

---

2. 상어 움직이기

fun moveSharks()
{
    var visited = Array(N + 1, {BooleanArray(N + 1)})

    first@for(i in (1 until sharkList.size).filter { i -> !isDead[i] })
    {
        var index = sharkList[i].index
        var x = sharkList[i].x
        var y = sharkList[i].y
        var dir = sharkList[i].dir

        //냄새 없는 곳부터 찾기
        for(j in 1..4)
        {
            var next = getNext(x, y, priority[index][dir][j])

            //맵 안에 있는지
            if(next[0] in 1..N && next[1] in 1..N)
            {
                //냄새가 없는 경우
                if(map[next[0]][next[1]] == 0)
                {
                    if(!visited[next[0]][next[1]])
                    {
                        visited[next[0]][next[1]] = true
                        sharkList[i].x = next[0]
                        sharkList[i].y = next[1]
                        sharkList[i].dir = priority[index][dir][j]
                        queue_smell[i].offer(Smell(next[0],next[1]))
                        //map[next[0]][next[1]] = index
                    }
                    else
                        isDead[index] = true
                    continue@first
                }
            }
        }

        //자기 냄새 있는 곳
        for(j in 1..4)
        {
            //현재 방향 기준 우선순위별로 다음 갈 곳
            var next = getNext(x, y, priority[index][dir][j])

            //맵 안에 있는지
            if(next[0] in 1..N && next[1] in 1..N)
            {
                //자기 냄새 남아있는 곳
                if(map[next[0]][next[1]] == index)
                {
                    sharkList[i].x = next[0]
                    sharkList[i].y = next[1]
                    sharkList[i].dir = priority[index][dir][j]
                    queue_smell[i].offer(Smell(next[0],next[1]))
                    //map[next[0]][next[1]] = index
                    continue@first
                }
            }
        }
    }
}

fun getNext(x : Int, y : Int, dir : Int) : Array<Int>
{
    var next = arrayOf(x, y)

    when (dir)
    {
        //위
        1 -> next[0]--
        //아래
        2 -> next[0]++
        //왼쪽
        3 -> next[1]--
        //오른쪽
        4 -> next[1]++
    }

    return next
}

 각 턴마다 상어들을 우선순위에 따라 움직이게 하는 모듈이다. 우선적으로 상어들은 냄새가 없는 곳으로 먼저 이동을 하기 때문에 냄새가 없는 칸을 찾고, 냄새가 없는 칸이 있다면 자기보다 번호가 낮은 상어가 방문했는지 검사 후, 자기보다 낮은 상어가 방문했다면 충돌이므로 해당 상어는 죽게 된다(isDead[i] = true). 방문을 아무도 안했다면 queue_smell에 현재 위치를 냄새 객체로 추가 하고 상어의 위치 정보를 갱신한다.

 

 만약 냄새가 없는 칸이 없다면 다시 우선순위에 따라서 자기 냄새가 있는 칸으로 이동시킨다.

---

3. 냄새 관련

//냄새 남기기
fun putSmell()
{
    for(i in (1 until sharkList.size).filter { i -> !isDead[i] })
    {
        var smell = queue_smell[i].last()
        map[smell.x][smell.y] = i
    }
}

//냄새빠짐
fun pollSmell()
{
    for(i in (1 until queue_smell.size).filter { i -> !queue_smell[i].isEmpty()})
    {
        var smell = queue_smell[i].poll()

        //똑같은 smell을 더 안포함하고 있으면
        if(!queue_smell[i].contains(smell))
            map[smell.x][smell.y] = 0
    }
}

 putSmell 메서드는 방금 추가된 smell들의 흔적을 map에 남기는 역할을 한다. map에는 각 상어의 번호로 남긴다.

 

 pollSmell은 각 턴마다 냄새들을 뺀다. 이 때 같은 위치의 Smell이 2개 이상 들어갈 수 있기 때문에 smell을 dequeu하더라도 해당 Smell과 같은 Smell이 queue에 들어 있으면 map은 그냥 놔둔다.

---

4. 메인

fun solution(){

    var str = readLine()!!.split(" ")
    N = str[0].toInt()
    M = str[1].toInt()//상어 마리 수
    K = str[2].toInt()//상어가 k번 이동하면 냄새가 사라짐

    isDead = BooleanArray(M + 1)
    isDead[0] = true
    map = Array<IntArray>(N + 1, {IntArray(N + 1)})
    sharkList = List<Shark>(M + 1,{i ->  Shark(i, 0, 0, 0)})
    queue_smell = Array(M + 1, {LinkedList<Smell>()})

    //맵 -> 상어 위치
    for(i in 1..N)
    {
        str = readLine()!!.split(" ")

        for(j in 1..N)
        {
            map[i][j] = str[j - 1].toInt()
            if(map[i][j] > 0)
            {
                sharkList[map[i][j]].x = i
                sharkList[map[i][j]].y = j
                queue_smell[map[i][j]].offer(Smell(i, j))
            }
        }
    }


    str = readLine()!!.split(" ")

    //방향 입력
    for(i in 1..M)
        sharkList[i].dir = str[i - 1].toInt()

    //각 상어마다의 우선순위 [상어번호][현재방향][우선순위별 방향]
    priority = Array<Array<IntArray>>(M + 1, {Array<IntArray>(5, { IntArray(5) })})

    for(i in 1..M)
    {
        for(j in 1..4)
        {
            str = readLine()!!.split(" ")
            priority[i][j][1] = str[0].toInt()
            priority[i][j][2] = str[1].toInt()
            priority[i][j][3] = str[2].toInt()
            priority[i][j][4] = str[3].toInt()
        }
    }


    for(i in 1..1000)
    {
        //이동
        moveSharks()
        putSmell()

        if(i >= K)
            pollSmell()

        //println(isDead.count { b -> b == false })
        if(isDead.count { b-> b == false } == 1 && !isDead[1]) //0번과 1번 -> 즉 1번 상어만 남아있으면 종료
        {
            print(i)
            return
        }
    }

    print(-1)
}

 다른 건 다 입력 정보를 받아 오는 것이고 맨 밑 반복문만 보자. 우선 값이 나올 수 있는 최소 범위는 1초~1000초까지이다. 난 1초부터 시작하기에 상어를 먼저 이동시키고 냄새 흔적을 남긴다. 그리고 상어들의 이동횟수가 K번이 넘어가게 되면 그 때부턴 무조건 queue_smell에서 각 턴마다 dequeue를 진행한다.

 그리고 살아있는 상어가 1마리이고 그 상어가 1번이라면 해당 시간을 출력 후 종료한다. 만약 1000번까지도 종료 조건이 성립하지 않으면 -1을 출력한다.

 

전체 코드이다.

import java.util.*
import kotlin.collections.ArrayList


lateinit var map : Array<IntArray>
lateinit var sharkList : List<Shark>
lateinit var queue_smell : Array<Queue<Smell>>
lateinit var priority : Array<Array<IntArray>>
lateinit var isDead : BooleanArray
var N : Int = 0
var M : Int = 0
var K : Int = 0


fun solution(){

    var str = readLine()!!.split(" ")
    N = str[0].toInt()
    M = str[1].toInt()//상어 마리 수
    K = str[2].toInt()//상어가 k번 이동하면 냄새가 사라짐

    isDead = BooleanArray(M + 1)
    isDead[0] = true
    map = Array<IntArray>(N + 1, {IntArray(N + 1)})
    sharkList = List<Shark>(M + 1,{i ->  Shark(i, 0, 0, 0)})
    queue_smell = Array(M + 1, {LinkedList<Smell>()})

    //맵 -> 상어 위치
    for(i in 1..N)
    {
        str = readLine()!!.split(" ")

        for(j in 1..N)
        {
            map[i][j] = str[j - 1].toInt()
            if(map[i][j] > 0)
            {
                sharkList[map[i][j]].x = i
                sharkList[map[i][j]].y = j
                queue_smell[map[i][j]].offer(Smell(i, j))
            }
        }
    }


    str = readLine()!!.split(" ")

    //방향 입력
    for(i in 1..M)
        sharkList[i].dir = str[i - 1].toInt()

    //각 상어마다의 우선순위 [상어번호][현재방향][우선순위별 방향]
    priority = Array<Array<IntArray>>(M + 1, {Array<IntArray>(5, { IntArray(5) })})

    for(i in 1..M)
    {
        for(j in 1..4)
        {
            str = readLine()!!.split(" ")
            priority[i][j][1] = str[0].toInt()
            priority[i][j][2] = str[1].toInt()
            priority[i][j][3] = str[2].toInt()
            priority[i][j][4] = str[3].toInt()
        }
    }


    for(i in 1..1000)
    {
        //이동
        moveSharks()
        putSmell()

        if(i >= K)
            pollSmell()

        //println(isDead.count { b -> b == false })
        if(isDead.count { b-> b == false } == 1 && !isDead[1]) //0번과 1번 -> 즉 1번 상어만 남아있으면 종료
        {
            print(i)
            return
        }
    }

    print(-1)
}

fun moveSharks()
{
    var visited = Array(N + 1, {BooleanArray(N + 1)})

    first@for(i in (1 until sharkList.size).filter { i -> !isDead[i] })
    {
        var index = sharkList[i].index
        var x = sharkList[i].x
        var y = sharkList[i].y
        var dir = sharkList[i].dir

        //냄새 없는 곳부터 찾기
        for(j in 1..4)
        {
            var next = getNext(x, y, priority[index][dir][j])

            //맵 안에 있는지
            if(next[0] in 1..N && next[1] in 1..N)
            {
                //냄새가 없는 경우
                if(map[next[0]][next[1]] == 0)
                {
                    if(!visited[next[0]][next[1]])
                    {
                        visited[next[0]][next[1]] = true
                        sharkList[i].x = next[0]
                        sharkList[i].y = next[1]
                        sharkList[i].dir = priority[index][dir][j]
                        queue_smell[i].offer(Smell(next[0],next[1]))
                        //map[next[0]][next[1]] = index
                    }
                    else
                        isDead[index] = true
                    continue@first
                }
            }
        }

        //자기 냄새 있는 곳
        for(j in 1..4)
        {
            //현재 방향 기준 우선순위별로 다음 갈 곳
            var next = getNext(x, y, priority[index][dir][j])

            //맵 안에 있는지
            if(next[0] in 1..N && next[1] in 1..N)
            {
                //자기 냄새 남아있는 곳
                if(map[next[0]][next[1]] == index)
                {
                    sharkList[i].x = next[0]
                    sharkList[i].y = next[1]
                    sharkList[i].dir = priority[index][dir][j]
                    queue_smell[i].offer(Smell(next[0],next[1]))
                    //map[next[0]][next[1]] = index
                    continue@first
                }
            }
        }
    }
}

fun getNext(x : Int, y : Int, dir : Int) : Array<Int>
{
    var next = arrayOf(x, y)

    when (dir)
    {
        //위
        1 -> next[0]--
        //아래
        2 -> next[0]++
        //왼쪽
        3 -> next[1]--
        //오른쪽
        4 -> next[1]++
    }

    return next
}

//냄새 남기기
fun putSmell()
{
    for(i in (1 until sharkList.size).filter { i -> !isDead[i] })
    {
        var smell = queue_smell[i].last()
        map[smell.x][smell.y] = i
    }
}

//냄새빠짐
fun pollSmell()
{
    for(i in (1 until queue_smell.size).filter { i -> !queue_smell[i].isEmpty()})
    {
        var smell = queue_smell[i].poll()

        //똑같은 smell을 더 안포함하고 있으면
        if(!queue_smell[i].contains(smell))
            map[smell.x][smell.y] = 0
    }
}

data class Shark(val index : Int, var dir : Int, var x : Int, var y : Int)

data class Smell(var x : Int, var y : Int)

fun main() {
    solution()
}