백준 18809 Gaaaaaaaaaarden Kotlin (시뮬레이션)

문제 출처: https://www.acmicpc.net/problem/18809

18809번: Gaaaaaaaaaarden

문제

길고 길었던 겨울이 끝나고 BOJ 마을에도 봄이 찾아왔다. BOJ 마을에서는 꽃을 마을 소유의 정원에 피우려고 한다. 정원은 땅과 호수로 이루어져 있고 2차원 격자판 모양이다.

인건비 절감을 위해 BOJ 마을에서는 직접 사람이 씨앗을 심는 대신 초록색 배양액과 빨간색 배양액을 땅에 적절하게 뿌려서 꽃을 피울 것이다. 이 때 배양액을 뿌릴 수 있는 땅은 미리 정해져있다.

배양액은 매 초마다 이전에 배양액이 도달한 적이 없는 인접한 땅으로 퍼져간다.

아래는 초록색 배양액 2개를 뿌렸을 때의 예시이다. 하얀색 칸은 배양액을 뿌릴 수 없는 땅을, 황토색 칸은 배양액을 뿌릴 수 있는 땅을, 하늘색 칸은 호수를 의미한다.

초록색 배양액과 빨간색 배양액이 동일한 시간에 도달한 땅에서는 두 배양액이 합쳐져서 꽃이 피어난다. 꽃이 피어난 땅에서는 배양액이 사라지기 때문에 더 이상 인접한 땅으로 배양액을 퍼트리지 않는다.

아래는 초록색 배양액 2개와 빨간색 배양액 2개를 뿌렸을 때의 예시이다.

배양액은 봄이 지나면 사용할 수 없게 되므로 주어진 모든 배양액을 남김없이 사용해야 한다. 예를 들어 초록색 배양액 2개와 빨간색 배양액 2개가 주어졌는데 초록색 배양액 1개를 땅에 뿌리지 않고, 초록색 배양액 1개와 빨간색 배양액 2개만을 사용하는 것은 불가능하다.

또한 모든 배양액은 서로 다른 곳에 뿌려져야 한다.

정원과 두 배양액의 개수가 주어져있을 때 피울 수 있는 꽃의 최대 개수를 구해보자.

입력

첫째 줄에 정원의 행의 개수와 열의 개수를 나타내는 N(2 ≤ N ≤ 50)과 M(2 ≤ M ≤ 50), 그리고 초록색 배양액의 개수 G(1 ≤ G ≤ 5)와 빨간색 배양액의 개수 R(1 ≤ R ≤ 5)이 한 칸의 빈칸을 사이에 두고 주어진다.

그 다음 N개의 줄에는 각 줄마다 정원의 각 행을 나타내는 M개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0, 1, 2이다. 0은 호수, 1은 배양액을 뿌릴 수 없는 땅, 2는 배양액을 뿌릴 수 있는 땅을 의미한다.

배양액을 뿌릴 수 있는 땅의 수는 R+G개 이상이고 10개 이하이다.

출력

첫째 줄에 피울 수 있는 꽃의 최대 개수를 출력한다.

노트

주어진 모든 배양액을 남김없이 사용해야 하고, 모든 배양액은 서로 다른 곳에 뿌려져야 함에 다시 한 번 유의한다.

알고리즘 분류

• 구현
• 그래프 이론
• 브루트포스 알고리즘
• 그래프 탐색
• 너비 우선 탐색
• 시뮬레이션

풀이

골드 1치고 나쁘지 않았던 시뮬레이션 문제~!

그럼에도 6번이나 틀렸다.

전체적인 풀이는 다음과 같다.

 

1. 조합으로 초록색 배양액, 빨간색 배양액의 세트를 구한다.

  - 그래프를 입력받을 때 배양액을 뿌릴 수 있는 칸의 좌표들을 저장해 놓는다.

2. 1번에서 구한 세트로 시뮬레이션을 돌린다.

3. 시뮬레이션은 bfs로 돌리며, turn과 q.size를 이용하여 현재 턴, 이전 턴, 아직 방문하지 않은 칸 등을 구분한다.

4. 아직 방문하지 않은 칸이면 배양액을 퍼뜨리고, 이전에 방문한 칸이면 스킵, 현재 턴에 다른 색의 배양액으로 방문했다면 꽃을 피운다.

 

본인은 처음에 초록색, 빨간색의 세트를 조합이 아닌 순열로 구해서 중복된 조합을 탐색하여 시간 초과가 났다.

여기서 말하는 중복이란, 초록색이 총 3개, 빨간색이 총 2개일 때 g1 g2 g3 r1 r2이라는 조합이 나왔다고 하면,

g1 r1 g2 r2 g3 는 다른 조합으로 유효한 결과지만,  g2 g1 g3 r2 r1은 같은 조합, 즉 중복이기 때문에 이는 검사할 필요가 없다.

    for(i in searchIdx until size){
        //그린 삽입
        if(g>0){
            startList[resultIdx] = Node(oilList[i].first, oilList[i].second, 0)
            combination(i+1,resultIdx+1,cnt+1,size,n,m,g-1,r)
        }
        //레드 삽입
        if(r>0) {
            startList[resultIdx] = Node(oilList[i].first, oilList[i].second, 1)
            combination(i+1,resultIdx+1,cnt+1,size,n,m,g,r-1)
        }
    }

따라서 위 코드가 초록색 배양액, 빨간색 배양액을 배치하는 핵심 코드라 할 수 있다.

 

이후 시뮬레이션은 bfs 응용으로 어렵지 않게 구현할 수 있다.

Node라는 data class에 r,c,color를 프로퍼티로 두고, 이를 큐에 담는다.

큐의 초기값은 위에서 구한 초록색, 빨간색 배양액들을 담고, bfs를 돌리면 된다. 

코드

import java.util.*
val br = System.`in`.bufferedReader()

data class Node(
    val r: Int,
    val c: Int,
    val color: Int
)
val oilList=ArrayList<Pair<Int,Int>>()
lateinit var graph: Array<IntArray>
lateinit var startList: Array<Node>
val dir = arrayOf(
    arrayOf(0,1),
    arrayOf(1,0),
    arrayOf(0,-1),
    arrayOf(-1,0)
)
var answer=0
//graph에 0만 아니면 이동은 가능
//꽃이 만들어지면 이동 제거
//도달한 적이 없는 데로만 퍼지기 가능
//조합으로 r과 g 세트를 생성
//생성된 조합으로 시뮬레이션 최댓값 갱신
//시뮬레이션할 때마다 그래프 복제하여 사용(원본 그래프 있어야 함)


//visited first : turn, second : color
fun simulation(n:Int, m: Int, spread: Array<Array<Pair<Int,Int>>>): Int{
    var sum=0
    val q: Queue<Node> = LinkedList()
    for(node in startList){
        q.add(node)
        spread[node.r][node.c]= Pair(-2,-1)
    }

    var turn=1
    while(q.isNotEmpty()){
        val size = q.size
        //한 턴에 두 배양액이 만나야만 ++
        for(i in 0 until size){
            val cur = q.poll()
            //꽃이 핀 부분은 스킵
            if(spread[cur.r][cur.c].first==0) continue
            for(i in 0 until 4){
                val nr = cur.r+dir[i][0]
                val nc = cur.c+dir[i][1]
                if(nr !in 0 until n || nc !in 0 until m) continue
                if(graph[nr][nc]==0) continue
                //꽃 피우기
                if(spread[nr][nc].first==turn){
                    if(spread[nr][nc].first>=0 && spread[nr][nc].second != cur.color) {
                        sum++
                        spread[nr][nc] = Pair(0,-1)
                    }
                }
                //새로 방문
                else if(spread[nr][nc].first==-1){
                    spread[nr][nc] = Pair(turn,cur.color)
                    q.add(Node(nr,nc,cur.color))
                }
                //이미 방문
                else continue
            }
        }
        turn++
    }
    return sum
}


fun combination(searchIdx: Int, resultIdx: Int,cnt: Int, size: Int, n: Int, m: Int, g: Int, r: Int){
    //g, r 모두 선별
    if(g==0 && r==0){
        answer = answer.coerceAtLeast(simulation(n,m,Array(n){Array(m){Pair(-1,-1)}}))
        return
    }
    //남은 땅으로 배양액을 모두 사용할 수 없으면 중단
    if(size-cnt < g+r) return

    for(i in searchIdx until size){
        //그린 삽입
        if(g>0){
            startList[resultIdx] = Node(oilList[i].first, oilList[i].second, 0)
            combination(i+1,resultIdx+1,cnt+1,size,n,m,g-1,r)
        }
        //레드 삽입
        if(r>0) {
            startList[resultIdx] = Node(oilList[i].first, oilList[i].second, 1)
            combination(i+1,resultIdx+1,cnt+1,size,n,m,g,r-1)
        }
    }
}


fun main() = with(System.out.bufferedWriter()){

    //input
    val (n,m,g,r) = br.readLine().split(' ').map{it.toInt()}
    graph = Array(n){
        val tk = StringTokenizer(br.readLine())
        IntArray(m){ tk.nextToken().toInt()}
    }
    for(i in 0 until n){
        for(j in 0 until m){
            if(graph[i][j]==2){
                oilList.add(Pair(i,j))
            }
        }
    }
    startList = Array(g+r){Node(0,0,0)}
    //solve
    combination(0,0,0,oilList.size,n,m,g,r)

    //output
    write("$answer")

    close()
}