[CodeTree] 나무박멸 (C++) [삼성 SW 역량테스트 기출]

https://www.codetree.ai/training-field/frequent-problems/problems/tree-kill-all

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

#include <iostream>
using namespace std;

int n, m, k, c, answer;
int map[20][20];

int dx1[4] = {0, 0, -1, 1};
int dy1[4] = {-1, 1, 0, 0};

int dx2[4] = {-1, -1, 1, 1};
int dy2[4] = {-1, 1, -1, 1};

void Growth(){
    for(int x = 0; x < n; x++){
        for(int y = 0; y < n; y++){
            if(map[x][y] > 0){
                for(int q = 0; q < 4; q++){
                    int nx = x + dx1[q];
                    int ny = y + dy1[q];

                    if(nx >= 0 && ny >= 0 && nx < n && ny < n){
                        if(map[nx][ny] > 0) map[x][y]++;
                    }
                }
            }
        }
    }
}

void Breeding(){
    int tmp[20][20] = {0, };
    for(int x = 0; x < n; x++){
        for(int y = 0; y < n; y++){
            if(map[x][y] > 0){
                int canBreed = 0;
                for(int q = 0; q < 4; q++){
                    int nx = x + dx1[q];
                    int ny = y + dy1[q];

                    if(nx >= 0 && ny >= 0 && nx < n && ny < n){
                        if(map[nx][ny] == 0) canBreed++;
                    }
                }

                for(int q = 0; q < 4; q++){
                    int nx = x + dx1[q];
                    int ny = y + dy1[q];

                    if(nx >= 0 && ny >= 0 && nx < n && ny < n){
                        if(map[nx][ny] == 0) tmp[nx][ny] += map[x][y] / canBreed;
                    }
                }
            }
        }
    }
    for(int x = 0; x < n; x++){
        for(int y = 0; y < n; y++){
            if(tmp[x][y] > 0) map[x][y] = tmp[x][y];
        }
    }
}

void Spread(){
    int maxdie = 0, maxrow = 0, maxcol = 0;
    for(int x = 0; x < n; x++){
        for(int y = 0; y < n; y++){
            if(map[x][y] <= 0) continue;
                
            int die = map[x][y];
            for(int q = 0; q < 4; q++){
                for(int p = 1; p <= k; p++){
                    int nx = x + dx2[q] * p;
                    int ny = y + dy2[q] * p;

                    if(nx >= 0 && ny >= 0 && nx < n && ny < n){
                        if(map[nx][ny] > 0) die += map[nx][ny];
                        else break;
                    }
                }
            }
            if(die > maxdie){
                maxdie = die;
                maxrow = x;
                maxcol = y;
            }
        }
    }
    answer += maxdie;
    map[maxrow][maxcol] = -2-c;
    for(int q = 0; q < 4; q++){
        for(int p = 1; p <= k; p++){
            int nx = maxrow + dx2[q] * p;
            int ny = maxcol + dy2[q] * p;
            if(nx >= 0 && ny >= 0 && nx < n && ny < n){
                if(map[nx][ny] == 0 || map[nx][ny] <= -2){
                    map[nx][ny] = -2-c;
                    break;
                } else if(map[nx][ny] == -1){
                    break;
                } else{
                    map[nx][ny] = -2-c;
                }
            }
        }
    }
}

int main() {
    cin >> n >> m >> k >> c;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cin >> map[i][j];
        }
    }

    for(int year = 1; year <= m; year++){
        Growth();  // 1
        Breeding();  // 2

        // 제초제 기간 감소
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(map[i][j] < -2) map[i][j]++;
                if(map[i][j] == -2) map[i][j] = 0;
            }
        }

        Spread();  // 3
    }
    cout << answer;
    return 0;
}

 

2번 과정과 3번 과정 사이에 제초제 시간을 감소시켜야 한다. (그림 참조)

 

제초제를 뿌린 칸을 -2-c로 설정하고 c년이 지나 -2가 되면 빈칸(0)이 되도록 하였는데 이것 때문에 헷갈렸다.

제초제 기간을 담는 배열을 따로 만드는 것이 더 나을 것 같다.