[6개월 안에 백준 플래티넘 달성하기] 8. 테트로미노 14500 | 코틀린
2023. 10. 25 ~ 2023. 11. 19 백준 솔브 CLASS3 문제 풀이 완료, 골드 5
Class 3까지 모든 문제를 클리어했습니다. Class 3에는 새로운 알고리즘 유형의 문제인 bfs, dfs, dp 문제가 많이 보였습니다. 아직까지는 해당 알고리즘 유형의 기본적인 문제만 있기에 큰 어려움 없이 해결할 수 있었습니다. 오히려 구현문제가 더 어려웠던 거 같습니다.결국 코테를 잘하는 방법은 [알고리즘 유형에 대한 이해 + 구현] 이 아닐까 싶습니다. 그런 의미에서 단순한 브루트포스 방법으로도 풀 수 있지만, 더 깔끔한 구현을 통해 더 좋은 해결책을 찾을 수 있는 테트로미노 문제를 가져오게 되었습니다.
문제
첫 번째 풀이
가장 무난한 방법은 N x M를 돌면서 테트리스의 모든 경우를 체크해 주는 것입니다.
체크해줘야 할 테트리스의 경우는 총 23개입니다. (8개의 경우 반전의 경우가 존재)
수 작업이긴 하지만 테트리트마다 좌표값을 지정해 주면 쉽게 풀 수 있습니다.
fun main() = with(System.`in`.bufferedReader()) {
val (N, M) = readLine().split(" ").map { it.toInt() }
val arr = Array(N) { readLine().split(" ").map { it.toInt() }}
테트로미노.arr = arr
val tetris1 = arrayOf (
/**
* 0 0
* 0 0
*/
Pair(arrayOf(1,1,0), arrayOf(0,1,1)),
/**
* 0 0 0 0
*/
/**
* 0
* 0
* 0
* 0
*/
Pair(arrayOf(1,2,3), arrayOf(0,0,0)),
Pair(arrayOf(0,0,0), arrayOf(1,2,3)),
/**
* 0 0 0 0 0 0
* 0 0 0 0 0 0 0 0
* 0 0
*/
Pair(arrayOf(0,1,-1), arrayOf(-1,0,0)),
Pair(arrayOf(0,-1,1), arrayOf(1,0,0)),
Pair(arrayOf(-1,0,0), arrayOf(0,-1,1)),
Pair(arrayOf(0,1,0), arrayOf(-1,0,1))
)
// 반전이 있는 테트리스
val tetris2 = arrayOf(
/**
* 0 0 0 0 0 0 0
* 0 0 0 0 0 0
* 0 0 0
* x값 -로 바꾸면 반전
*/
Pair(arrayOf(0,0,1), arrayOf(-1,-2,0)),
Pair(arrayOf(0,1,2), arrayOf(-1,-1,-1)),
Pair(arrayOf(1,1,1), arrayOf(0,1,2)),
Pair(arrayOf(1,2,2), arrayOf(0,0,-1)),
/**
* 0 0 0 0 0 0
* 0 0 0 0 0 0 0 0
* 0 0
* x값 -로 바꾸면 반전
*/
Pair(arrayOf(0,1,1), arrayOf(-1,0,1)),
Pair(arrayOf(1,1,2), arrayOf(0,-1,-1)),
Pair(arrayOf(0,1,1), arrayOf(1,1,2)),
Pair(arrayOf(1,1,2), arrayOf(0,-1,-1))
)
var result = 0
for (i in 0..<N) {
for (j in 0..<M) {
val tResult1 = 테트로미노.check(i, j, tetris1, false, M, N)
if (tResult1 != 0) {
result = Math.max(result, tResult1)
}
// 반전이 아닌 경우
val tResult2 = 테트로미노.check(i, j, tetris2, false, M, N)
if (tResult2 != 0) {
result = Math.max(result, tResult2)
}
// 반전인 경우
val tResult3 = 테트로미노.check(i, j, tetris2, true, M, N)
if (tResult3 != 0) {
result = Math.max(result, tResult3)
}
}
}
print(result)
}
object 테트로미노 {
lateinit var arr: Array<List<Int>>
fun check(y: Int, x: Int, tetris: Array<Pair<Array<Int>, Array<Int>>>, isTwist: Boolean, M: Int, N:Int) : Int{
var count = 0
for (tet in tetris) {
var tCount = arr[y][x]
val dy = tet.second
val dx = tet.first
var isTet = true
for (i in dy.indices) {
val nextY = y + dy[i]
val nextX = if (!isTwist) x + dx[i] else x + dx[i] * -1
if (nextY < 0 || nextX < 0 || nextX >= M || nextY >= N) {
isTet = false
break
}
tCount += arr[nextY][nextX]
}
if (isTet) {
count = Math.max(count, tCount)
}
}
return count
}
}
두 번째 풀이
본인은 전혀 생각지도 못한 풀이 방법인데 다른 풀이방법이 있는지 찾아보다가 알게 되었습니다.
dfs를 이용하면 되는 기막힌 방법인데
위 모양에서 분홍 테트리스를 제외하면 dfs의 깊이가 4인 모든 경우에 해당 테트리스가 모두 포함됩니다.
어떤 경우든 테트리스 모양이 나오기 때문에 우리는 각각의 테트리스를 신경 써주지 않아도 됩니다.
실제로 위 그림에서 적용시켜 보시면 쉽게 이해가 되실 겁니다.
분홍 테트리스가 dfs에 포함이 안 되는 이유는 모양 자체가 dfs로 나올 수 없어서 인데 깊이가 2인 지점에서 두 갈래로 나누어지기 때문입니다.
이를 해결해 주기 위해서는 dfs의 깊이가 2일 때 한 번 더 dfs를 진행해 주면 됩니다.
다만 기존 dfs와의 차이점은 다음 좌표값이 아닌 현재 좌표값을 다시 한번 전달하는 것입니다. 이러면 결과적으로 분홍 테트리스 모양을 얻을 수 있습니다.
fun main() = with(System.`in`.bufferedReader()) {
val (N, M) = readLine().split(" ").map { it.toInt() }
val arr = Array(N) { readLine().split(" ").map { it.toInt() }}
val visited = Array(N){BooleanArray(M)}
val dx = intArrayOf(-1, 1, 0, 0)
val dy = intArrayOf(0, 0, -1, 1)
var max = 0
fun dfs(y: Int, x: Int, sum: Int, count: Int) {
if (count == 4) {
max = Math.max(max, sum)
return
}
for (i in 0..<4) {
val nextY = y + dy[i]
val nextX = x + dx[i]
if (nextY < 0 || nextX < 0 || nextX >= M || nextY >= N) {
continue
}
if (!visited[nextY][nextX]) {
// 분홍 테트리스의 경우
if (count == 2) {
visited[nextY][nextX] = true
dfs(y, x, sum + arr[nextY][nextX], count + 1)
visited[nextY][nextX] = false
}
visited[nextY][nextX] = true
dfs(nextY, nextX, sum + arr[nextY][nextX], count + 1)
visited[nextY][nextX] = false
}
}
}
for (i in 0..<N) {
for (j in 0..<M) {
visited[i][j] = true
dfs(i, j, arr[i][j], 1)
visited[i][j] = false
}
}
print(max)
}