(BOJ) 14263 카드 놓기

14263 카드 놓기

• 분류 : 위상 정렬

문제

영선이는 카드와 그리드를 가지고 놀고 있다. 각각의 카드는 직사각형 모양이며, 색칠되어져 있다. 두 카드가 같은 색을 가지는 경우는 없으며, 크기도 카드마다 다를 수 있다.

영선이는 한 번에 카드 하나씩 그리드 위에 올려놓는다. 카드를 올려놓을 때, 그리드의 변과 평행이 되게 카드를 올려놓아야 한다. 따라서, 직사각형은 그리드의 칸을 덮게 된다. 또, 카드는 겹쳐서 놓을 수 있다. 카드가 놓이면서 어떤 카드를 완전히 가리는 경우는 없다.

카드를 다 놓은 다음, 위에서 바라본 결과가 주어진다. 이때, 카드를 놓은 순서를 구하는 프로그램을 작성하시오..

입력

첫째 줄에 그리드의 크기 N과 M이 주어진다. (1 ≤ N, M ≤ 50)

둘째 줄부터 N개의 줄에 그리드에 놓여진 카드의 색이 주어진다. 카드의 색은 알파벳 소문자(‘a’-‘z’), 대문자(‘A’-‘Z’), 숫자(‘0’-‘9’) 중 하나이며, ‘.’는 빈 칸이다.

출력

첫째 줄에 카드를 놓은 순서를 출력한다. 만약 가능한 순서가 여러 가지라면, 사전순으로 앞서는 것을 출력한다. 만약, 불가능한 경우에는 -1을 출력한다.

예제 입력 1

3 6
..AA..
.CAAC.
.CAAC.

예제 출력 1

CA

예제 입력 2

2 6
..47..
..74..

예제 출력 2

-1

예제 입력 3

5 6
bbb666
.655X5
a65AA5
a65AA5
a65555

예제 출력 3

65AXab

Solution

Exapnder

package boj

import java.util.*
import kotlin.collections.HashMap
import kotlin.math.min
import kotlin.math.max

private const val MAX = 51
private const val EMPTY = '.'

private var N: Int = 0
private var M: Int = 0

private lateinit var grid:Array<CharArray>
private var colorMap = HashMap<Char, Int>()
// a ~ z : 97 ~ 122
// A ~ Z : 65 ~ 90
// 0 ~ 9 : 48 ~ 57
private var colorId = CharArray(123)
private var count: Int = 0 // 색상 종류

private lateinit var above: Array<BooleanArray>

private var result: String = ""

fun main() {
    input()
    solve()
}

private fun input() = with(Scanner(System.`in`)) {
    N = nextInt()
    M = nextInt()

    init()

    for (i in 0 until N) {
        var str = next()
        for (j in 0 until M) {
            grid[i][j] = str[j]
        }
    }
}

private fun init() {
    // 입력받는 grid
    grid = Array(N) {
        CharArray(M) { '.' }
    }
}

private fun solve() {
    // 색상 종류 카운팅 및 초기화
    calcColorCount()

    // above[i][j] = 특정 색상값 i에 올라올 수 있는 색상값이 있느냐 없느냐를 구분
    above = Array(count) {
        BooleanArray(count) { false }
    }

    // 색상별 카드 범위 계산
    calcCardArea()
    // 계산 불가능한 경우의 예외 처리
    if (result == "-1") {
        println(result)
        return
    }

    topologicalSort()

    println("$result")
}

private fun printGraph(msg: String?) {
    msg?.let {
        println("=== $it")
    }
    for (i in 0 until N) {
        for (j in 0 until M) {
            print("${grid[i][j]} ")
        }
        println()
    }
}

private fun calcColorCount() {
    var index = 0
    for (i in 0 until N) {
        for (j in 0 until M) {
            var ch = grid[i][j]
            // 공백이 아니고, 아직 계산 안한 색상값이라면 추가
            if (ch != EMPTY && !colorMap.containsKey(ch)) {
                colorId[index] = ch
                colorMap[ch] = index
                index++
            }
        }
    }
    count = index
}

private fun calcCardArea() {
    // 계산한 총 색상의 종류만큼 반복
    for (i in 0 until count) {
        var minX = N - 1
        var maxX = -1
        var minY = M - 1
        var maxY = -1

        // 특정 색상값이 그리드에서 차지하고 있는 영역 계산
        for (x in 0 until N) {
            for (y in 0 until M) {
                if (grid[x][y] == colorId[i]) {
                    minX = min(minX, x)
                    maxX = max(maxX, x)
                    minY = min(minY, y)
                    maxY = max(maxY, y)
                }
            }
        }

        // 계산해낸 그리드의 영역내에 겹쳐진 색상값을 찾는다.
        for (x in minX .. maxX) {
            for (y in minY .. maxY) {
                // 계산하는 영역이 공백이면 가능한 순서가 존재하지않음
                if (grid[x][y] == EMPTY) {
                    result = "-1"
                    return
                }
                // 다른 색상값이 존재하면 현재 계산중인 색상의 카드 위에 다른 카드가 존재할 수 있음
                if (grid[x][y] != colorId[i]) {
                    var color = grid[x][y]
                    if (colorMap.containsKey(color)) {
                        above[i][colorMap[color]!!] = true
                    }
                }
            }
        }
    }
}

private fun topologicalSort() {
    var removed = BooleanArray(count) { false }
    for (i in 0 until count) {
        var pick = 'z' + 1 // 최대값 123
        var target = -1 // 최솟값

        // 색상만큼 순회
        for (j in 0 until count) {
            if (removed[j]) {
                continue
            }
            // 밑에 깔려있다면 result에 추가한다.
            var isBelow = true
            // 제거 되지않은 색상이면서, 위에 있는 카드가 아닌 경우
            for (k in 0 until count) {
                isBelow = isBelow and (removed[k] || !above[k][j])
            }
            if (isBelow) {
                if (pick > colorId[j]) {
                    target = j
                    pick = colorId[j]
                }
                if (j < target && pick == colorId[j]) {
                    target = j
                }
            }
        }

        // 계산 불가능한 경우
        if (target == -1) {
            result = "-1"
            return
        }
        result += pick
        // 계산한 색상은 제외
        removed[target] = true
    }
}

Point of Thinking

• 주어진 grid에서 유니크한 색상값들을 먼저 카운팅해야 한다.
  • 결국 색상값의 종류들을 어떻게 나열할지 결정하는 문제이기 때문
  • 색상값의 범위는 a-z, A-Z, 0-9 이므로 122칸의 배열의 인덱스로 표현할 수 있다.
• 카드는 직사각형 형태이므로, 해당 카드의 고윳값의 좌상단, 좌하단, 우상단, 우하단의 좌표값을 통해 영역을 추출할 수 있다.
  • 주어진 영역내에 다른 색상값이 존재한다면, 계산중인 카드 위에 또 다른 카드가 올라와있다고 볼 수 있다.
    • 이는 기존 카드를 완전히 덮어쓰는 카드는 없다는 문제의 조건에서 추측할 수 있다. (애초에 이러면 문제가 성립이 안되긴 하지만)
• 색상 종류와 카드 영역 계산을 통한 덮어쓰기 유무까지 추출했다면 이를 바탕으로 위상 정렬을 수행한다.
  • 위상 정렬 && 계산한 색상을 배제하기 위해 제거된 색상 관리를 위한 배열을 조건에 추가한 뒤, 올라올 수 있는 카듸 조건에 부합하면 결과값에 추가하면 된다.
• 문제가 매우 복잡해서 solve() 함수안에서 다 작성하기가 힘들었기때문에 문제를 분할한 뒤, 각각 메서드로 분리하여 풀었다.
  • 생각이 미친 부분들은 주석을 추가해가면서 수행하여 Accepted.