[알고리즘] 나무 재테크

포인트

1. 구현을 잘 할 수 있는가? map 을 2개를 쓰는 것, map 안에 vector 를 잘 사용할 수 있는 것

2. (영양분을 저장하는 곳, 기본적으로 나눠주는 map, ) 봄 여름 가을 겨울

봄에서 그냥 벡터를 하나 만들고 대체를 하는 방식으로 구현을 했습니다. 

봄하고 여름은 합체

2021 03 14 수정

• 가을하고 겨울도 합체
• 파이썬 버전 추가

 

🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. 

c++/cpp

#include<iostream>
#include<algorithm>
#include<vector>


using namespace std;

int n, m, k;
int nut[11][11];
int machine[11][11];

vector<int> map[11][11];

int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};


void spring_summer() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (map[i][j].empty()) continue;

            int die = 0;
            vector<int> live;

            sort(map[i][j].begin(), map[i][j].end()); // 나이어린 순으로 정렬
            for (auto ele :map[i][j]) {
                if (nut[i][j] >= ele) {
                    nut[i][j] -= ele;
                    live.push_back(ele + 1);
                } else die += (ele / 2);
            }

            map[i][j] = live; // 살아있는 나무로 교체
            nut[i][j] += die; //죽은 만큼 양분으로 돌아간다
        }
    }
}

void fall() { // 나무 번식
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (map[i][j].empty()) continue;

            for (auto ele : map[i][j]) {
                if (ele % 5 == 0) { // 5의 배수
                    for (int a = 0; a < 8; a++) { //8개 구역에서
                        int nx = i + dx[a];
                        int ny = j + dy[a];

                        if (nx < 0 || ny < 0 || nx > n || ny > n) continue;
                        map[nx][ny].push_back(1); //1 인 나무가 생긴다.
                    }
                }
            }
        }
    }
}

void winter() { // 기계가 이것만큼 양분을 준다.
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            nut[i][j] += machine[i][j];
        }
    }
}

int main() {
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> machine[i][j];
            nut[i][j] = 5; // 양분
        }
    } //input

    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        map[--a][--b].push_back(c);
    }
    for (int i = 0; i < k; i++) {
        spring_summer();
        fall();
        winter();
    }

    int answer = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            answer += map[i][j].size();
        }
    }

    cout << answer << endl;

    return 0;
}

python

from collections import deque

n, m, k = map(int, input().split())

machine = [list(map(int, input().split())) for _ in range(n)] # 기계 양분값
nutrition = [[5] * n for _ in range(n)]
tree = [[deque() for _ in range(n)] for _ in range(n)]

for _ in range(m):
    x, y, z = map(int, input().split())
    tree[x - 1][y - 1].append(z) # 나무 나이 등록

dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]


def spring_and_summer():
    for i in range(n):
        for j in range(n):
            temp = deque()
            die = 0
            for ele in sorted(tree[i][j]):
                if nutrition[i][j] - ele >= 0:
                    nutrition[i][j] -= ele
                    temp.append(ele + 1)
                else:
                    die += ele // 2
            tree[i][j] = temp
            nutrition[i][j] += die


def fall_and_winter():
    for i in range(n):
        for j in range(n):
            for ele in tree[i][j]:
                if ele % 5 == 0:
                    for dir in range(8):
                        nx, ny = i + dx[dir], j + dy[dir]
                        if not (0 <= nx < n and 0 <= ny < n):
                            continue
                        tree[nx][ny].appendleft(1)
            nutrition[i][j] += machine[i][j]


for _ in range(k):
    spring_and_summer()
    fall_and_winter()

cnt = 0
for i in range(n):
    for j in range(n):
        cnt += len(tree[i][j])
print(cnt)