문제 소개
🥇️ 문제 레벨 : 골드3
🔔 문제 유형 : 구현, 시뮬레이션, 브루트포스
💬 풀이 언어 : Kotlin
🖇️ 문제 링크 : 백준 문제 링크
📝 문제
혜윤이는 최근에 다양한 대회를 참여하면서 노트북에 붙일 수 있는 스티커들을 많이 받았다. 스티커는 아래와 같이 사각 모눈종이 위에 인쇄되어 있으며, 스티커의 각 칸은 상하좌우로 모두 연결되어 있다. 또한 모눈종이의 크기는 스티커의 크기에 꼭 맞아서, 상하좌우에 스티커가 포함되지 않는 불필요한 행이나 열이 존재하지 않는다.
혜윤이는 자신의 노트북에 이 스티커들을 붙이기로 했다. 혜윤이의 노트북은 마침 직사각형 모양이고, 스티커가 인쇄된 모눈종이와 같은 간격으로 격자가 그려져 있다. 혜윤이는 스티커들을 먼저 받았던 것부터 차례대로 격자에 맞춰서 붙이려고 한다.
혜윤이가 스티커를 붙이는 방법은 다음과 같다.
- 스티커를 회전시키지 않고 모눈종이에서 떼어낸다.
- 다른 스티커와 겹치거나 노트북을 벗어나지 않으면서 스티커를 붙일 수 있는 위치를 찾는다. 혜윤이는 노트북의 위쪽부터 스티커를 채워 나가려고 해서, 스티커를 붙일 수 있는 위치가 여러 곳 있다면 가장 위쪽의 위치를 선택한다. 가장 위쪽에 해당하는 위치도 여러 곳이 있다면 그중에서 가장 왼쪽의 위치를 선택한다.
- 선택한 위치에 스티커를 붙인다. 만약 스티커를 붙일 수 있는 위치가 전혀 없어서 스티커를 붙이지 못했다면, 스티커를 시계 방향으로 90도 회전한 뒤 2번 과정을 반복한다.
- 위의 과정을 네 번 반복해서 스티커를 0도, 90도, 180도, 270도 회전시켜 봤음에도 스티커를 붙이지 못했다면 해당 스티커를 붙이지 않고 버린다.
혜윤이는 스티커를 다 붙인 후의 노트북의 모습이 궁금해졌다. 노트북의 크기와 스티커들이 주어졌을 때 스티커들을 차례대로 붙이고 난 후 노트북에서 몇 개의 칸이 채워졌는지 구해보자.
🤔 문제 분석
우선 알고리즘 분석을 해봤다. 스티커가 주어지고, 그 스티커를 90도씩 돌려가면서 노트북에 붙여야하기 때문에 구현 + 시뮬레이션이 확실함을 느꼈다. 즉, 가능한 모든 경우의 수를 대입하면서 확인해야하는 브루트 포스를 사용해야한다.
1초에 약 1억 번의 연산이 가능하다고 가정하고, 문제의 조건을 분석해보자.
- 스티커 최대 개수: 100
- 노트북 최대 크기: 40 x 40
- 스티커 최대 크기: 10 x 10
- 회전 횟수: 4
100 * 4 * (40 * 40) * (10 * 10)으로 총 6,400,000번의 연산으로 2초 내에 충분히 통과할 수 있다.
이제 이 문제를 풀기 위한 핵심 로직들을 나눠서 정리해보자.
도형 회전
우선, 문제에서 나온 것과 같이 모눈 종이의 크기는 r * c 형태이다.
val shape = Array(r) { IntArray(c) }문제의 예시 중 2번 도형을 가져와보자. 이 도형은 -ㅜ 모양이며, 그래프로 나타낼 경우, 0, 1, 2, 3, 4, 8번이 스티커로 이루어진 모눈 종이이다. 이 스티커를 90도 뒤집으면서 회전 코드를 만들어보자.
-- 원본 --
[0, 1, 2, 3, 4]
[5, 6, 7, 8, 9]
-- 90도 회전 후 --
[5, 0]
[6, 1]
[7, 2]
[8, 3]
[9, 4]보는 것과 같이 배열의 구조 자체가 바뀌게 된다. 이를 코드로 나타내보자.
// 원본
val shape = Array(r) { IntArray(c) }
val originRows = shape.size
val originCols = shape[0].size
// 회전된 배열
val rotated = Array(c) { IntArray(r) }
val rotatedRows = rotated.size
val rotatedCols = rotated[0].size우선 배열 구조는 위와 같이 바뀌게 된다. 그렇다면 데이터는 어떨까? 원본의 0번 행이 회전 후 각 행의 끝 열에 들어가게 되고, 원본의 1번 행은 각 행의 끝 열 - 1에 들어가게 된다. 즉, 식과 코드로 나타내면 다음과 같은 것이다.
- 원본: 0번 행 -> 회전: 각 행의
originRows - 1번 열 - 원본: 1번 행 -> 회전: 각 행의
originRows - 1 - 1번 열 - 원본: 2번 행 -> 회전: 각 행의
originRows - 1 - 2번 열
for (r in 0 until originRows) {
for (c in 0 until originCols) {
newShape[c][originRows - 1 - r] = shape[r][c]
}
}배치 가능 여부 확인
1. 스티커 범위 확인
우선, 스티커를 노트북에 붙일 수 있는지 확인해야 한다. 만약, 스티커의 가로 크기가 노트북의 가로 크기를 벗어나거나, 스티커의 세로 크기가 노트북의 세로 크기를 벗어날 경우 회전을 시켜야 한다. 노트북의 크기가 2(세로) * 4(가로)라고 가정해보자. 만약, 스티커가 4(세로) * 1(가로)인 경우 회전을 하면 붙일 수 있기 때문에 꼭 필요한 로직이다.
for (rotate in 0..3) {
if (sticker.rows > n || sticker.cols > m) {
sticker.rotate()
continue
}
...
}2. 스티커를 붙일 수 있는 좌표 탐색
스티커를 붙일 수 있다면, 어디에 붙일지 확인을 해야한다. 하지만, 모든 범위를 다 검사하기에는 너무 많은 범위를 탐색하게 된다. 우리는 필요하지 않은 부분은 굳이 탐색하지 않도록 최적화를 시켜야 한다.
이는, 문제에 힌트로 제공되어 있다. 스티커를 붙일 때는, 노트북의 왼쪽 위부터 붙인다는 조건이 나와있다. 즉, 우리가 탐색할 범위는 노트북의 왼쪽 위부터 스티커를 붙였을 때, 스티커가 완전히 붙을 수 있는 범위만 탐색하면 되는 것이다.
만약 크기가 3 * 3인 노트북에 2 * 2 크기의 스티커를 붙인다고 가정해보자. 이 스티커를 붙일 수 있는 위치는 다음과 같을 것이다.
[1, 1, 0] -> [0, 1, 1] -> [0, 0, 0] -> [0, 0, 0]
[1, 1, 0] -> [0, 1, 1] -> [1, 1, 0] -> [0, 1, 1]
[0, 0, 0] -> [0, 0, 0] -> [1, 1, 0] -> [0, 1, 1]즉, 노트북의 크기가 n * m이고, 스티커의 크기가 rows * cols일 때, 스티커의 왼쪽 상단 꼭지점이 위치할 수 있는 위치는 다음과 같이 제한적이게 된다.
- 세로 범위 : 0 ~ (n - rows)
- 가로 범위 : 0 ~ (m - cols)
for (i in 0..(n - sticker.rows)) {
for (j in 0..(m - sticker.cols)) {
...
}
...
}3. 스티커 붙이기
스티커를 붙일 좌표를 선정했다면, 그 위치에 스티커를 붙일 수 있는지 확인하면 된다. 만약 붙이지 못할 경우 회전시켜서 다시 확인하면 끝이다.
우선, 앞에서 얻은 (i, j)를 활용해서 스티커를 붙일 수 있는지 확인해보자. Sticker 클래스에 있는 shape는 사실상 모눈 종이이고, 그 위에 1로 된 데이터가 실제 스티커가 있는 위치이다.
즉, 스티커를 붙일 노트북의 위치에 이미 스티커가 붙어있다면 바로 false를 반환하면 되는 것이고, 만약 모두 붙일 수 있다면 true를 반환해주면 되는 것이다.
private fun canPlace(
laptop: Array<IntArray>, sticker: Sticker, i: Int, j: Int
): Boolean {
for (r in 0 until sticker.rows) {
for (c in 0 until sticker.cols) {
if (sticker.shape[r][c] == 1 && laptop[i + r][j + c] == 1) {
return false
}
}
}
return true
}이 canPlace 함수를 조금만 수정하면 laptop에 스티커를 붙일 수 있게 된다.
private fun place(
laptop: Array<IntArray>, sticker: Sticker, i: Int, j: Int
) {
for (r in 0 until sticker.rows) {
for (c in 0 until sticker.cols) {
if (sticker.shape[r][c] == 1) {
laptop[i + r][j + c] = 1
}
}
}
}😎 최종 코드
메모리 : 26496 KB
시간 : 168 msimport java.util.*
private class Sticker(var shape: Array<IntArray>) {
var rows: Int = shape.size
var cols: Int = if (shape.isEmpty()) 0 else shape[0].size
fun rotate() {
if (rows == 0 || cols == 0) return
val newShape = Array(cols) { IntArray(rows) }
for (r in 0 until rows) {
for (c in 0 until cols) {
newShape[c][rows - 1 - r] = shape[r][c]
}
}
shape = newShape
rows = shape.size
cols = shape[0].size
}
}
fun main() = with(System.`in`.bufferedReader()) {
val (n, m, k) = StringTokenizer(readLine()).run {
Triple(
nextToken().toInt(), nextToken().toInt(), nextToken().toInt()
)
}
val laptop = Array(n) { IntArray(m) { 0 } }
repeat(k) {
val (r, c) = StringTokenizer(readLine()).run {
nextToken().toInt() to nextToken().toInt()
}
val shape = Array(r) {
StringTokenizer(readLine()).run {
IntArray(c) { nextToken().toInt() }
}
}
val sticker = Sticker(shape)
for (rotate in 0..3) {
if (sticker.rows > n || sticker.cols > m) {
sticker.rotate()
continue
}
var placed = false
for (i in 0..(n - sticker.rows)) {
for (j in 0..(m - sticker.cols)) {
if (canPlace(laptop, sticker, i, j)) {
place(laptop, sticker, i, j)
placed = true
break
}
}
if (placed) break
}
if (placed) break
sticker.rotate()
}
}
println(laptop.sumOf { it.sum() })
}
private fun canPlace(
laptop: Array<IntArray>, sticker: Sticker, i: Int, j: Int
): Boolean {
for (r in 0 until sticker.rows) {
for (c in 0 until sticker.cols) {
if (sticker.shape[r][c] == 1 && laptop[i + r][j + c] == 1) {
return false
}
}
}
return true
}
private fun place(
laptop: Array<IntArray>, sticker: Sticker, i: Int, j: Int
) {
for (r in 0 until sticker.rows) {
for (c in 0 until sticker.cols) {
if (sticker.shape[r][c] == 1) {
laptop[i + r][j + c] = 1
}
}
}
}