(BOJ) 14263 카드 놓기

14263 카드 놓기

  • 분류 : 위상 정렬

문제

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

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

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

입력

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

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

출력

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

예제 입력 1

1
2
3
4
3 6
..AA..
.CAAC.
.CAAC.

예제 출력 1

1
CA

예제 입력 2

1
2
3
2 6
..47..
..74..

예제 출력 2

1
-1

예제 입력 3

1
2
3
4
5
6
5 6
bbb666
.655X5
a65AA5
a65AA5
a65555

예제 출력 3

1
65AXab

Solution

Exapnder
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
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.