문제 출처 : https://www.acmicpc.net/problem/20061
20061번: 모노미노도미노 2
모노미노도미노는 아래와 같이 생긴 보드에서 진행되는 게임이다. 보드는 빨간색 보드, 파란색 보드, 초록색 보드가 그림과 같이 붙어있는 형태이다. 게임에서 사용하는 좌표 (x, y)에서 x는 행,
www.acmicpc.net
문제
모노미노도미노는 아래와 같이 생긴 보드에서 진행되는 게임이다. 보드는 빨간색 보드, 파란색 보드, 초록색 보드가 그림과 같이 붙어있는 형태이다. 게임에서 사용하는 좌표 (x, y)에서 x는 행, y는 열을 의미한다. 빨간색, 파란색, 초록색 보드가 사용하는 좌표는 그 색으로 그림에 적혀있다.
<그림 1> 모노미노도미노 게임 보드
이 게임에서 사용하는 블록은 타일 하나 또는 두 개가 가로 또는 세로로 붙어있는 형태이다. 아래와 같이 세 종류가 있으며, 왼쪽부터 순서대로 크기가 1×1, 1×2, 2×1 이다.
<그림 2> 모노미노도미노 게임에서 사용하는 블록
블록을 놓을 위치를 빨간색 보드에서 선택하면, 그 위치부터 초록색 보드로 블록이 이동하고, 파란색 보드로 블록이 이동한다. 블록의 이동은 다른 블록을 만나거나 보드의 경계를 만나기 전까지 계속해서 이동한다. 예를 들어, 크기가 1×1인 블록을 (1, 1)에 놓으면, 보드의 상태는 <그림 3>과 같이 변한다.
<그림 3>
여기서 크기가 1×2인 블록을 (3, 0)과 (3, 1)에 놓으면 <그림 4>와 같이 보드의 상태가 변한다.
<그림 4>
다시 이 상태에서 크기가 2×1인 블록을 (2, 2), (3, 2)와 (2, 3), (3, 3)에 놓으면 <그림 5>와 같이 변한다.
<그림 5>
초록색 보드의 4번 행은 모든 칸이 타일로 가득 차있다. 이렇게 초록색 보드에서 어떤 행이 타일로 가득 차 있다면, 그 행의 타일은 모두 사라진다. 사라진 이후에는 초록색 보드에서 사라진 행의 위에 있는 블록이 사라진 행의 수만큼 아래로 이동한다. 파란색의 경우는 열이 타일로 가득 차 있으면, 그 열의 타일이 모두 사라지며, 사라진 이후에는 파란색 보드에서 사라진 열의 왼쪽에 있는 블록이 사라진 열의 수만큼 오른쪽으로 이동한다. 이렇게 한 행이나 열이 타일로 가득 차서 사라지면 1점을 획득한다. 점수는 사라진 행 또는 열의 수와 같다. 만약, 두 개의 행이 사라지면 2점을 획득하게 되고, 한 행과 한 열이 사라져도 2점을 획득하게 된다. 위의 보드는 아래와 같이 변하고, 1점을 얻는다.
<그림 6>
여기서 크기가 2×1인 블록을 (1, 3), (2, 3)에 놓으면 보드는 <그림 7>과 같이 변한다.
<그림 7>
초록색 보드의 0, 1번 행과 파란색 보드의 0, 1번 열은 그림에는 연한색으로 표현되어 있는 특별한 칸이다. 초록색 보드의 0, 1번 행에 블록이 있으면, 블록이 있는 행의 수만큼 아래 행에 있는 타일이 사라지고, 초록색 보드의 모든 블록이 사라진 행의 수만큼 아래로 이동하고, 파란색 보드의 0, 1번 열에 블록이 있으면, 블록이 있는 열의 수만큼 오른쪽 열에 있는 타일이 사라지고, 파란색 보드의 모든 블록이 사라진 열의 수만큼 이동하게 된다. 위의 그림은 파란색 보드의 1번 열에 블록이 있기 때문에, 5번 열에 있는 블록이 모두 사라지고, 파란색 보드의 모든 블록이 오른쪽으로 한 칸 이동하게 된다. 따라서, 보드는 <그림 8>과 같이 변하게 된다.
<그림 8>
위의 보드에서 1×2인 블록을 (0, 0), (0, 1)에 놓으면 <그림 9>와 같다.
<그림 9>
여기서 크기가 2×1인 블록을 (2, 0), (3, 0)에 놓으면 <그림 10>과 같이 변한다. 파란색 보드는 1번 열에 블록이 생겨서 오른쪽으로 한 칸씩 이동한 상태이다.
<그림 10>
크기가 2×1인 블록을 (1, 2), (2, 2)에 놓으면, <그림 11>과 같이 변한다.
<그림 11>
파란색 보드는 1번 열에 블록이 있기 때문에, 5번 열의 타일이 사라지고 모든 블록이 오른쪽으로 한 칸씩 이동하게 된다. 초록색 보드는 4번 행의 모든 칸에 타일이 있기 때문에, 1점을 얻으면서, 4번 행의 모든 타일이 사라진다.
<그림 12>
<그림 12>는 <그림 11>의 상태에서 파란색 보드는 모든 블록이 오른쪽으로 한 칸 이동했고, 초록색 보드의 4번 행이 모두 사라진 상태이다. 이제, 초록색 보드에서 사라진 행의 위에 있는 블록이 아래로 한 칸씩 내려와야 한다. 이동한 후의 상태는 <그림 13>과 같다.
<그림 13>
행이나 열이 타일로 가득찬 경우와 연한 칸에 블록이 있는 경우가 동시에 발생할 수 있다. 이 경우에는 행이나 열이 타일로 가득 찬 경우가 없을 때까지 점수를 획득하는 과정이 모두 진행된 후, 연한 칸에 블록이 있는 경우를 처리해야 한다.
블록은 보드에 놓인 이후에 다른 블록과 합쳐지지 않는다. 블록을 놓은 위치가 순서대로 주어졌을 때, 얻은 점수와 초록색 보드와 파란색 보드에 타일이 있는 칸의 개수를 모두 구해보자.
입력
첫째 줄에 블록을 놓은 횟수 N(1 ≤ N ≤ 10,000)이 주어진다.
둘째 줄부터 N개의 줄에 블록을 놓은 정보가 한 줄에 하나씩 순서대로 주어지며, t x y와 같은 형태이다.
- t = 1: 크기가 1×1인 블록을 (x, y)에 놓은 경우
- t = 2: 크기가 1×2인 블록을 (x, y), (x, y+1)에 놓은 경우
- t = 3: 크기가 2×1인 블록을 (x, y), (x+1, y)에 놓은 경우
블록이 차지하는 칸이 빨간색 칸의 경계를 넘어가는 경우는 입력으로 주어지지 않는다.
출력
첫째 줄에 블록을 모두 놓았을 때 얻은 점수를 출력한다.
둘째 줄에는 파란색 보드와 초록색 보드에서 타일이 들어있는 칸의 개수를 출력한다.
알고리즘 분류
풀이
삼성 기출 구현 문제다.
조건대로 구현하면 되는 문제라 딱히 알고리즘이 필요하진 않다. 그냥 구현하면 된다.
단지 주의할 점은, blue영역이든 green영역이든 블럭이 떨어질 때 수평 블럭이 떨어지는 경우를 주의해야 한다.
<그림 8> 처럼 1*2 블럭이 떨어지는데 이 블럭에서 한 칸이 걸린다면 나머지 한 블럭은 아래로 떨어지지 않고 그 블럭 전체가 그 걸린 곳에 걸치게 된다.
본인은 green, blue 두 개의 그래프를 생성해놓고, green에 블럭을 떨굴 땐 그대로 입력 그대로 떨구고, blue에 블럭을 떨굴 땐 블럭을 오른쪽으로 돌려서 떨궜다.
이때 떨구는 블럭이 가로 모양인지 확인하고 가로모양인 경우 그래프의 어떤 블럭 위에 올라오게 된다면 걸치게끔 해두었다.
나머지 블럭을 떨구는 것은 그냥 해당 블럭이 떨어지는 자리에 기존 블럭이 있는곳의 위에 위치시키면 된다.
블럭을 성공적으로 떨궜으면 이제 연한 색깔 영역에 블럭이 있는지, 터뜨릴 행이 있는지 확인해야 한다.
순서는 터뜨릴 행이 있다면 먼저 터뜨린 후 행을 땡겨주고, 그다음 연한 색깔 영역에 블럭이 있다면 또 행을 땡겨주자.
연한 색깔 영역은 터뜨리는 것에 영향을 받지 않기 때문에 어떠한 행을 터뜨리고 행을 땡긴다 해도 연한 색깔 영역은 그대로 냅두자.
코드
val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().split(' ').map { it.toInt() }
fun getInt() = br.readLine().toInt()
val blue = Array(6) { IntArray(4) }
val green = Array(6) { IntArray(4) }
var answer = 0
var sumAnswer = 0
fun changeRC(r: Int, c: Int): Pair<Int, Int> {
val rr = c
val cc = 3 - r
return Pair(rr, cc)
}
lateinit var temp: Array<IntArray>
fun makeBlock(t: Int, x: Int, y: Int): Array<IntArray> {
if (t == 1) {
temp = Array(1) { intArrayOf(x, y) }
} else if (t == 2) {
temp = Array(2) { IntArray(2) }
temp[0] = intArrayOf(x, y)
temp[1] = intArrayOf(x, y + 1)
} else {
temp = Array(2) { IntArray(2) }
temp[0] = intArrayOf(x, y)
temp[1] = intArrayOf(x + 1, y)
}
return temp
}
fun move(color: String, horizon: Boolean, block: Array<IntArray>) {
val y = block[0][1]
when (color) {
"green" -> {
for (r in 0..5) {
if (horizon) {
val y2 = block[1][1]
if (green[r][y] + green[r][y2] != 0) {
if (r - 1 >= 0) {
green[r - 1][y] = 1
green[r - 1][y2] = 1
}
break
}
if (r == 5) {
green[r][y] = 1
green[r][y2] = 1
}
} else {
if (green[r][y] == 1) {
if (r - 1 >= 0) green[r - 1][y] = 1
if (r - 2 >= 0 && block.size > 1) green[r - 2][y] = 1
break
}
if (r == 5) {
green[r][y] = 1
if (block.size > 1) green[r - 1][y] = 1
}
}
}
}
"blue" -> {
for (r in 0..5) {
if (horizon) {
val y2 = block[1][1]
if (blue[r][y] + blue[r][y2] != 0) {
if (r - 1 >= 0) {
blue[r - 1][y] = 1
blue[r - 1][y2] = 1
}
break
}
if (r == 5) {
blue[r][y] = 1
blue[r][y2] = 1
}
} else {
if (blue[r][y] == 1) {
if (r - 1 >= 0) blue[r - 1][y] = 1
if (r - 2 >= 0 && block.size > 1) blue[r - 2][y] = 1
break
}
if (r == 5) {
blue[r][y] = 1
if (block.size > 1) blue[r - 1][y] = 1
}
}
}
}
else -> {
}
}
}
fun bomb() {
var greenScore = 0
//점수 획득
var r = 5
while (r >= 2) {
var sum = green[r].sum()
if (sum == 4) {
greenScore++
green[r][0] = 0
green[r][1] = 0
green[r][2] = 0
green[r][3] = 0
//폭발 후 땡기기
for (c in 0..3) {
for (r1 in r downTo 1) {
green[r1][c] = green[r1 - 1][c].also { green[r1 - 1][c] = 0 }
}
}
r++
}
r--
}
//연한 색깔 영역에 블럭이 있는 경우 땡기기
var downCnt = 0
for (rr in 0..1) {
if (green[rr].sum() > 0) {
downCnt++
}
}
if (downCnt > 0) {
for (r in 5 downTo 0) {
for (c in 0..3) {
if (r - downCnt < 0) {
green[r][c] = 0
} else {
green[r][c] = green[r - downCnt][c]
}
}
}
}
var blueScore = 0
//점수 획득
r = 5
while (r >= 2) {
var sum = blue[r].sum()
if (sum == 4) {
blueScore++
blue[r][0] = 0
blue[r][1] = 0
blue[r][2] = 0
blue[r][3] = 0
//폭발 후 땡기기
for (c in 0..3) {
for (r1 in r downTo 1) {
blue[r1][c] = blue[r1 - 1][c].also { blue[r1 - 1][c] = 0 }
}
}
r++
}
r--
}
//연한 색깔 영역에 블럭이 있는 경우 땡기기
downCnt = 0
for (rr in 0..1) {
if (blue[rr].sum() > 0) {
downCnt++
}
}
if (downCnt > 0) {
for (r in 5 downTo 0) {
for (c in 0..3) {
if (r - downCnt < 0) {
blue[r][c] = 0
} else {
blue[r][c] = blue[r - downCnt][c]
}
}
}
}
answer += greenScore + blueScore
}
fun simulation(t: Int, x: Int, y: Int) {
val block = makeBlock(t, x, y)
var horizon = false
if (t == 2) horizon = true
//한 블럭 이동
move("green", horizon, block)
for (i in block.indices) {
val (r, c) = changeRC(block[i][0], block[i][1])
block[i][0] = r
block[i][1] = c
}
horizon = false
if (t == 3) horizon = true
move("blue", horizon, block)
bomb()
}
fun main() = with(System.out.bufferedWriter()) {
//input
val n = getInt()
//solve
repeat(n) {
val (t, x, y) = getIntList()
simulation(t, x, y)
}
for (r in 2..5) {
for (c in 0..3) {
sumAnswer += green[r][c] + blue[r][c]
}
}
//output
write("$answer\n")
write("$sumAnswer")
close()
}'알고리즘 문제 풀이 > 백준' 카테고리의 다른 글
| 백준 14503 로봇 청소기 Kotlin (시뮬레이션) (0) | 2022.07.17 |
|---|---|
| 백준 1301 비즈 공예 Kotlin (dp) (0) | 2022.07.16 |
| 백준 18427 함께 블록 쌓기 Kotlin (dp) (0) | 2022.07.15 |
| 백준 2011 암호코드 Kotlin (dp) (0) | 2022.07.13 |
| 백준 1976 여행 가자 Kotlin (플로이드 와샬) (0) | 2022.07.12 |
댓글