백준 17085 십자가 2개 놓기 Kotlin (완전 탐색)

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

17085번: 십자가 2개 놓기

문제

십자가는 가운데에 '*'가 있고, 상하좌우 방향으로 모두 같은 길이의 '*'가 있는 모양이다. 십자가의 크기는 가운데를 중심으로 상하좌우 방향으로 있는 '*'의 개수이다. 십자가의 크기는 0보다 크거나 같아야 한다.

아래 그림은 크기가 0, 1, 2, 3인 십자가이고, 빈 칸은 '.'이다.

                  ...*...
          ..*..   ...*...
    .*.   ..*..   ...*...
*   ***   *****   *******
    .*.   ..*..   ...*...
          ..*..   ...*...
                  ...*...

십자가의 넓이는 포함된 '*'의 개수이다. 크기가 0, 1, 2, 3인 십자가의 넓이는 1, 5, 9, 13이다.

크기가 N×M이고, '.'과 '#'로 이루어진 격자판이 주어진다. 격자판에 두 개의 십자가를 겹치지 않게 놓으려고 한다. 십자가는 '#'가 있는 칸에만 놓을 수 있다. 놓인 십자가 넓이의 곱의 최댓값을 구해보자.

입력

첫째 줄에 격자판의 크기 N, M (2 ≤ N, M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에 격자판의 상태가 주어진다. 항상 두 개의 십자가를 놓을 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 놓은 십자가 넓이의 곱의 최댓값을 출력한다.

알고리즘 분류

• 구현
• 브루트포스 알고리즘

풀이

완전 탐색 문제이다.

주어진 그래프에서 두 개의 십자가를 고르는 모든 경우를 탐색하여 두 십자가의 넓이를 곱해준다.

 

두 십자가 넓이의 곱은 아래 함수처럼 구하면 된다.

fun getTwoCrossArea(len1: Int, len2: Int) = (1 + len1 * 4) * (1 + len2 * 4)

 

아래 solve함수가 두 개의 십자가를 고르는 함수이다.

fun solve(n: Int, m: Int, idx: Int, cnt: Int, pprevLen: Int, prevLen: Int)

idx : 2차원 그래프의 1차원 인덱스

cnt : 선택한 십자가의 개수

pprevLen : 전전에 선택한 십자가의 개수

prevLen : 전에 선택한 십자가의 개수

 

1차원 인덱스를 이용해

r  = idx/m

c = idx%m

으로 행과 열을 구하고,

현재 좌표가 #이라면 십자가를 만들고 cnt를 늘려서 solve를 재귀 호출하는 것으로 두 번째 십자가를 구한다.

십자가를 만들 땐 현재 좌표에서 4방향을 탐색하여 최소 길이를 구한 후, 만약 최소 길이가 2라고 하면

0짜리 십자가를 만들고 두 번째 십자가 만들기

1짜리 십자가를 만들고 두 번째 십자가 만들기

2짜리 십자가를 만들고 세 번째 십자가 만들기

이렇게 십자가를 만들 수 있는 좌표에 대해서 항상 최대 크기의 십자가를 만드는 것이 아닌 0부터 가능한 길이까지의 십자가를 만드는 경우를 모두 탐색해야 한다.

이 과정은 아래 handleCross 함수와 getCrossLength 함수를 이용하고 handleCross 함수는 그래프에서 # -> *으로 바꾸고, * -> #으로 바꾸어주는 함수이다.

이렇게 십자가를 만드는 것을 그래프의 #을 *으로 바꾸는 것으로 구현한다.

 

이 문제에선 모든 가능한 두 가지 십자가를 탐색하는 solve를 함수를 이해하는 것이 가장 중요하다.

코드

val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().trim().split(' ').map { it.toInt() }
fun getInt() = br.readLine().trim().toInt()

val dir = arrayOf(
    arrayOf(0, 1),
    arrayOf(1, 0),
    arrayOf(0, -1),
    arrayOf(-1, 0)
)
var answer = 0
lateinit var graph: List<CharArray>

fun getTwoCrossArea(len1: Int, len2: Int) = (1 + len1 * 4) * (1 + len2 * 4)

//바꿔주기
fun handleCross(r: Int, c: Int, len: Int) {
    graph[r][c] = if (graph[r][c] == '#') '*' else '#'
    for (i in 0 until 4) {
        var nr = r
        var nc = c
        for (l in 0 until len) {
            nr += dir[i][0]
            nc += dir[i][1]
            graph[nr][nc] = if (graph[nr][nc] == '#') '*' else '#'
        }
    }
}

//네 방향 검사하여 최소 길이 구하기
fun getCrossLength(r: Int, c: Int): Int {
    var minLength = Int.MAX_VALUE
    for (i in 0 until 4) {
        var nr = r + dir[i][0]
        var nc = c + dir[i][1]
        var len = 0
        while (nr in graph.indices && nc in graph[0].indices && graph[nr][nc] == '#') {
            nr += dir[i][0]
            nc += dir[i][1]
            len++
        }
        if (len == 0) return 0
        minLength = minLength.coerceAtMost(len)
    }
    return minLength
}

fun solve(n: Int, m: Int, idx: Int, cnt: Int, pprevLen: Int, prevLen: Int) {
    if (cnt == 2) {
        answer = answer.coerceAtLeast(getTwoCrossArea(pprevLen, prevLen))
        return
    }
    if (idx >= n * m) return
    val r = idx / m
    val c = idx % m
    if (graph[r][c] == '#') {
        val minLen = getCrossLength(r, c)
        for (i in 0..minLen) {
            handleCross(r, c, i)
            solve(n, m, idx + 1, cnt + 1, prevLen, i)
            handleCross(r, c, i)
        }
    }
    solve(n, m, idx + 1, cnt, pprevLen, prevLen)
}

fun main() = with(System.out.bufferedWriter()) {
    //input
    val (n, m) = getIntList()
    graph = List(n) { br.readLine().toCharArray() }
    //solve
    solve(n, m, 0, 0, 0, 0)
    //output
    write("$answer")
    close()
}