[백준 16932] - 모양 만들기(Kotlin)[골드3]

문제

https://www.acmicpc.net/problem/16932

16932번: 모양 만들기

 

문제 풀이

항상 높은 난도의 BFS, DFS를 풀면 알 수 있듯이 최적화에 가장 신경을 써야 한다.

그렇지 않다면 무수히 많은 시간초과를 볼 수 있을 것이다...

문제의 핵심은 빈칸을 선택해서 사각형으로 바꾸고, 가장 길게 연결된 사각형의 크기를 구하는 것이다.

그렇다면 우리는 기존의 배열에서 사각형들을 라벨링 하는 것이 필요하다.

왜 라벨링을 해야하는가에 대해서 작업의 흐름을 판단하면 납득이 갈 것이다.

나도 초기 풀이에서는 빈칸중 하나를 선택해서 무식하게 쭉쭉 연결된 사각형들을 구했다.

즉 라벨링을 하지 않는다면 빈칸 선택, 사각형들을 탐색하는 과정이 계속해서 반복된다.

하지만 사각형들을 라벨링한다면, 빈칸을 선택하고, 라벨링 한 사각형의 그룹에 주변에 있는지 없는지만 판단하면 된다.

즉 사각형들을 매번 탐색하는 과정이 라벨링 하나로 생략된다.

라벨링에 대해서 간단하게 설명하자면, 연속된 사각형들을 그룹으로 나누는 것이다.

5 4
1 1 0 0  1 1 0 0
1 0 1 0  1 0 2 0
1 0 1 0  1 0 2 0
0 1 1 0  0 2 2 0
1 0 0 1  3 0 0 4

이렇게 쭈욱 연결해서 더이상 갈 수 있는 사각형이 없는 경우 새로운 그룹으로 결정한다.

그리고 그룹별로 몇개의 사각형이 연결되었는지 기록해야 한다.

이렇게 라벨링 했다면 그다음 과정은 정말 간단하다.

 

빈칸을 결정하고, 빈칸을 4방향으로 탐색하고 걸쳐져 있는 그룹이 있는 경우를 판단한다.

걸쳐져 있는 그룹이 있다면 해당 그룹의 사각형 개수를 더해주면 된다.

이런 식으로 모든 빈칸에 대해서 구해주면 문제를 풀 수 있을 것이다.

 

실제로 나는 bfs() 함수에서 check를 boolean 배열로 설정했는데, 시간초과가 발생했다.

따라서 set으로 바꿔서 check에 대한 여부만 판단했고, 시간초과를 해결했다.

 

전체 코드

package Graph.`16932_모양_만들기`

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.LinkedList
import java.util.Queue
import kotlin.math.max

class `16932` {

    private val br = BufferedReader(InputStreamReader(System.`in`))
    private var n = 0
    private var m = 0
    private lateinit var ary: Array<Array<Int>>
    private lateinit var group: Array<Array<Int>>
    private val x = arrayOf(1, -1, 0, 0)
    private val y = arrayOf(0, 0, 1, -1)
    private var answer = 0
    private val groupMember = mutableListOf<Int>()
    private val zeroQ: Queue<Pair<Int, Int>> = LinkedList()
    private val q: Queue<Pair<Int, Int>> = LinkedList()
    var groupLabel = 0

    init {
        input()
        select()
        print(answer)
    }

    private fun input() {
        var line = br.readLine().split(" ")
        n = line[0].toInt()
        m = line[1].toInt()
        ary = Array(n, { Array(m, { 0 }) })
        group = Array(n, { Array(m, { 0 }) })
        for (i in 0 until n) {
            line = br.readLine().split(" ")
            for (j in 0 until m) {
                ary[i][j] = line[j].toInt()
                if (ary[i][j] == 0) zeroQ.add(Pair(i, j))
                else q.add(Pair(i, j))
            }
        }
    }

    private fun labelGroup(row: Int, col: Int) {
        groupLabel++
        var cnt = 1
        val tempQ: Queue<Pair<Int, Int>> = LinkedList()
        group[row][col] = groupLabel
        tempQ.add(Pair(row, col))
        while (!tempQ.isEmpty()) {
            val item = tempQ.poll()
            for (dir in 0 until 4) {
                val moveX = item.first + x[dir]
                val moveY = item.second + y[dir]
                if ((moveX !in ary.indices) || (moveY !in ary[moveX].indices))
                    continue
                if (ary[moveX][moveY] == 0)
                    continue
                if (group[moveX][moveY] != 0)
                    continue
                group[moveX][moveY] = groupLabel
                tempQ.add(Pair(moveX, moveY))
                cnt++
            }
        }
        groupMember.add(cnt)
    }

    private fun select() {
        groupMember.add(0)
        while (!q.isEmpty()) {
            val item = q.poll()
            if (group[item.first][item.second] != 0)
                continue
            labelGroup(item.first, item.second)
        }
        while (!zeroQ.isEmpty()) {
            val item = zeroQ.poll()
            bfs(item.first, item.second)
        }
    }

    private fun bfs(row: Int, col: Int) {
        val check: HashSet<Int> = hashSetOf<Int>()
        var cnt = 1
        for (dir in 0 until 4) {
            val moveX = row + x[dir]
            val moveY = col + y[dir]
            if ((moveX !in ary.indices) || (moveY !in ary[moveX].indices))
                continue
            if (ary[moveX][moveY] == 0)
                continue
            if (check.contains(group[moveX][moveY]))
                continue
            check.add(group[moveX][moveY])
            cnt += groupMember[group[moveX][moveY]]
        }
        answer = max(answer, cnt)
    }
}

fun main() {
    val solution = `16932`()
}