https://www.acmicpc.net/problem/16235
난이도 : 골드 3
태그 : 구현, 자료구조, 시뮬레이션
설명
1년에 봄, 여름, 가을, 겨울. 네 계절 이있습니다.
봄에는 나무가 양분을 빨아먹고, 나이가 증가하며, 양분이 없는 나무는 죽습니다.
여름에는 죽은 나무가 양분으로 변합니다.
가을에는 나무가 번식합니다. 8방향에 나이가 1인 나무가 생겨나죠.
겨울에는 토양에 새 양분을 추가합니다.
딱히 별도의 알고리즘이나 테크닉 없이 문제 내용을 그대로 구현+시뮬레이션 하는 문제입니다.
소스코드
import java.util.StringTokenizer
data class Tree(val x: Int, val y: Int, var age: Int, var isDeath: Boolean = false)
lateinit var trees: MutableList<Tree>
lateinit var map: Array<Array<Int>>
lateinit var add: Array<Array<Int>>
val dx = arrayOf(0, 0, 1, -1, 1, -1, 1, -1)
val dy = arrayOf(1, -1, 0, 0, -1, 1, 1, -1)
var n = 0
fun main() = with(System.`in`.bufferedReader()) {
val nmk = readLine().split(" ").map { it.toInt() }
n = nmk[0]
val m = nmk[1]
val k = nmk[2]
// 모든 땅의 초기 양분은 5
map = Array(n) { Array(n) { 5 } }
// 1년당 추가되는 양분
add = Array(n) {
val st = StringTokenizer(readLine())
Array(n) { st.nextToken().toInt() }
}
// 새 나무가 계속 추가될 예정이기 때문에 나이 순 내림차순 정렬
trees = Array(m) {
val st = StringTokenizer(readLine())
Tree(st.nextToken().toInt() - 1, st.nextToken().toInt() - 1, st.nextToken().toInt())
}.sortedByDescending { it.age }.toMutableList()
// k년이 지난 후
repeat(k) {
spring()
summer()
autumn()
winter()
}
println(trees.size)
}
fun spring() {
// 새로운 1살짜리 나무가 계속 추가되기 때문에 역순으로 반복
for (i in trees.size - 1 downTo 0) {
if (map[trees[i].x][trees[i].y] - trees[i].age >= 0) {
map[trees[i].x][trees[i].y] -= trees[i].age
trees[i].age++
} else {
trees[i].isDeath = true
}
}
}
fun summer() {
trees.forEach { tree ->
if (tree.isDeath) map[tree.x][tree.y] += (tree.age / 2)
}
// 죽은 나무 제거
trees.removeIf { it.isDeath }
}
fun autumn() {
for (i in 0 until trees.size) {
if (trees[i].age % 5 != 0)
continue
for (j in 0 until 8) {
val nx = trees[i].x + dx[j]
val ny = trees[i].y + dy[j]
if (nx !in 0 until n || ny !in 0 until n) continue
// 새 나무 추가
trees.add(Tree(nx, ny, 1))
}
}
}
fun winter() {
repeat(n) { x ->
repeat(n) { y ->
map[x][y] += add[x][y]
}
}
}
단, 주의할 점은 나무가 나이가 적은 나무부터 양분을 빨아먹고,
계속 새로운 나무가 리스트에 추가될 예정이기 때문에,
나무 입력을 받은 뒤, 나이를 기준으로 내림차순 정렬을 해주었습니다.
같은 이유로, 봄 계절 시뮬레이션 과정 중, 나이가 적은 나무부터 양분을 흡수하기 위해
역순으로 반복문을 수행하였습니다.
코드 해석
1. 나무 정보를 담을 클래스 Tree 생성, 여기에는 x, y 좌표, 나이, 생사여부가 있음
2. k년 동안 봄-여름-가을-겨울 시뮬레이션
2-1. 봄 - spring() 메서드
역순으로 반복문 수행. 이는 나이가 적은 나무부터 영양분을 흡수하기 위함입니다.
땅의 양분이 충분하지 않다면 isDeath를 true 처리
2-2. 여름 - summer() 메서드
isDepth인 나무들을 찾아 나이 / 2 만큼 땅에 영양분 추가.
isDepth인 나무들을 리스트에서 제거
2-3. 가을 - autumn() 메서드
나이가 5의 배수이면 인접한 8방향에 나무를 심음.
2-4. 겨울 - winter() 메서드
땅에 영양분을 공급해줌
후기
딱히 머리 굴릴 필요 없이 문제 내용을 그대로 구현하기만 하면 됬던 문제라,
꽤 재밌게 풀었었습니다.
'코딩테스트 > Kotlin' 카테고리의 다른 글
[백준 7287번] [Kotlin] 등록 (0) | 2023.05.21 |
---|---|
[백준 14503번] [Kotlin] 로봇 청소기 (0) | 2023.05.14 |
[백준 10844번] [Kotlin] 쉬운 계단 수 (0) | 2023.05.12 |
[백준 13418번] [Kotlin] 학교 탐방하기 (0) | 2023.05.11 |
[백준 2250번] [Kotlin] 트리의 높이와 너비 (1) | 2023.05.10 |