백준 14712 넴모넴모 (Easy) Kotlin (백트래킹)

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

14712번: 넴모넴모 (Easy)

문제

네모는 뿌××× 게임에 깊은 감명을 받아, 직사각형 모양의 격자판과 “넴모”라는 수수께끼의 생물을 이용하는 “넴모넴모”라는 게임을 만들었다. 이 게임의 규칙은 아주 간단하다. 격자판의 비어 있는 칸을 임의로 골라 “넴모”를 하나 올려놓거나, “넴모”가 올라간 칸 네 개가 2 × 2 사각형을 이루는 부분을 찾아 그 위에 있는 “넴모”들을 모두 없애는 것을 질릴 때까지 반복하면 된다.

하지만 안타깝게도 게임은 정말 재미가 없었고, 네모는 아주 빨리 질려 버리고 말았다. 실망한 네모는 게임을 적당히 플레이하다가, “넴모”를 없애고 싶은데 격자판 위에 없앨 수 있는 “넴모”가 없으면 게임을 그만두기로 했다. 네모가 게임을 그만두었을 때 나올 수 있는 “넴모”의 배치의 가짓수를 구하여라.

입력

첫 번째 줄에 격자판의 행의 개수 N, 열의 개수 M(1 ≤ N, M ≤ 25, 1 ≤ N × M ≤ 25)이 공백으로 구분되어 주어진다.

출력

첫 번째 줄에 주어진 격자판에서 나올 수 있는, “넴모”들이 올라간 칸이 2 × 2 사각형을 이루지 않는 모든 배치의 가짓수를 출력한다.

힌트

2×2 격자판에 2×2 사각형을 이루지 않도록 “넴모”들을 배치하는 방법은 모든 경우(24 = 16) 중 네 칸 모두에 “넴모”가 올라가 있는 경우를 제외한 15가지가 있다.

알고리즘 분류

• 백트래킹

풀이

넴모넴모.. 문제를 잘 이해해야 한다.

넴모넴모가 터지는 조건은 인접 방향으로 4개가 이어졌을 때가 아닌, 2*2크기의 정사각형이 되었을 때다.

문제에선 넴모가 터질 수 없는 그래프의 상태의 모든 경우를 요구한다.

즉 우리는 모든 상태를 탐색하되 넴모가 터질 수 있는(2*2크기의 넴모넴모가 완성되는 경우)를 걸러줘야 한다.

이를 단순히 모든 경우를 구하고, 거기서 2*2넴모넴모가 있는지 검사하여 빼주는 것은

총 25칸에 각각 넴모를 넣은 상태, 넴모를 넣지 않은 상태로 총 2^25개의 경우가 나오므로 시간 초과가 나온다.

여기서 백트래킹 기법으로 2*2가 완성되는 경우는 더 이상 탐색을 진행하지 않음으로써 탐색 범위를 훨씬 줄일 수 있다.

 

햇김 로직인 backTracking 함수를 설명하자면,

2차원 인덱스를 1차원 인덱스로 변환하여 다음 칸을 탐색하는 것을 구현하고,

다시 2차원 인덱스로 변환 후, 현재 칸에 넴모를 넣을 수 있는지 검사한다.

넴모를 넣을 수 있다면 현재 칸에 넴모를 넣은 상태로 다음 칸을 탐색한다.

 

현재 칸에 넴모를 넣을 수 있든 없든, 다음 칸 탐색을 꼭 해주어야 한다.

 

넴모를 넣을 수 있는지 검사하는 것은 그래프의 탐색을 왼쪽 위부터 오른쪽 아래로 탐색하기 때문에,

현재 칸의 왼쪽, 왼쪽 위, 위 칸을 검사하여 이 세 칸이 모두 넴모가 들어있으면 넴모를 넣을 수 없다.

 

코드

val br = System.`in`.bufferedReader()
val dir = arrayOf(arrayOf(-1, 0), arrayOf(0, -1), arrayOf(-1, -1))
var answer = 0
lateinit var graph: Array<BooleanArray>

//왼,왼위,위가 true가 아닌 경우 블럭 넣을 수 있음
fun canBlock(r: Int,c:Int, n: Int, m: Int): Boolean {

    for (i in 0 until 3) {
        val nr = r + dir[i][0]
        val nc = c + dir[i][1]
        if (nr !in 0 until n || nc !in 0 until m) return true
        if (!graph[nr][nc]) return true
    }
    return false
}

fun backTracking(n: Int, m: Int, i: Int) {

    if (i == n * m) {
        answer++
        return
    }
    var idx = i
    val r = idx / m
    val c = idx % m
    graph[r][c] = true
    //현재 칸에 넴모를 넣을 수 없는 경우는 더 이상 탐색 x
    if (canBlock(r,c, n, m)) {
        backTracking(n, m, idx + 1)
    }
    //현재 칸에 넴모를 안 넣으면 그냥 다음 칸 탐색하면 됨
    graph[r][c] = false
    backTracking(n, m, idx + 1)
}

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

    val (n, m) = br.readLine().split(' ').map { it.toInt() }
    graph = Array(n) { BooleanArray(m) }
    backTracking(n, m, 0)

    write("$answer")
    close()
}