Uknow's Lab.
article thumbnail

https://www.acmicpc.net/problem/16235

 

16235번: 나무 재테크

부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터

www.acmicpc.net

 

난이도 : 골드 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() 메서드

땅에 영양분을 공급해줌

 

 

 

 

후기

딱히 머리 굴릴 필요 없이 문제 내용을 그대로 구현하기만 하면 됬던 문제라,

꽤 재밌게 풀었었습니다.

profile

Uknow's Lab.

@유노 Uknow

인생은 Byte와 Double 사이 Char다. 아무말이나 해봤습니다.