[코드트리] 나무박멸 - 시뮬레이션 (기출문제)

삼성 SW 역량테스트 2022 상반기 기출 

나무박멸

n * n 격자에 나무의 그루 수와 벽의 정보가 주어집니다.

나무의 성장과 번식력이 좋아서 제초제를 뿌려 나무의 성장을 억제하고자 합니다. 제초제의 경우 k의 범위만큼 대각선으로 퍼지며, 벽이 있는 경우 가로막혀서 전파되지 않습니다. 다음과 같이 초기 조건이 주어진다고 가정할 때, 1년동안 나무의 성장과 억제는 다음과 같이 이뤄집니다.

1. 인접한 네 개의 칸 중 나무가 있는 칸의 수만큼 나무가 성장합니다. 성장은 모든 나무에게 동시에 일어납니다.

(중략)

 

각 3개의 과정이 1년에 걸쳐 진행된다고 했을 때, m년 동안 총 박멸한 나무의 그루 수를 구하는 프로그램을 작성해보세요.

입력 형식

첫 번째 줄에 격자의 크기 n, 박멸이 진행되는 년 수 m, 제초제의 확산 범위 k, 제초제가 남아있는 년 수 c가 공백을 사이에 두고 주어집니다.

이후 n개의 줄에 걸쳐 각 칸의 나무의 그루 수, 벽의 정보가 주어집니다. 총 나무의 그루 수는 1 이상 100 이하의 수로, 빈 칸은 0, 벽은 -1으로 주어지게 됩니다.

• 5 ≤ n ≤ 20
• 1 ≤ m ≤ 1000
• 1 ≤ k ≤ 20
• 1 ≤ c ≤ 10

출력 형식

m년 동안 총 박멸한 나무의 그루 수를 구하세요.

---

 

제공된 예제 테스트케이스가 모두 맞기까지 1시간 반이 걸렸다.

근데 제출하니 테케 7번에서 틀림!!

 

근데 잘못된거 몇개 고쳤는데 계속 답이 작은 범위로 틀리게 나오는거임

ㅠ 3시간동안 계속 고쳐도 틀려서 그냥 포기하고 해설을 봐버렸다~~^^ 화딱지나

 

 

해설 풀이

#include <iostream>

#define MAX_N 20
#define DIR_NUM 4

using namespace std;

int n, m, k, c;
int tree[MAX_N + 1][MAX_N + 1];
int add_tree[MAX_N + 1][MAX_N + 1];
int herb[MAX_N + 1][MAX_N + 1];

int ans;

bool IsOutRange(int x, int y) {
    return !(1 <= x && x <= n && 1 <= y && y <= n);
}

// 입력을 받는 등 초기 작업을 합니다.
void Init() {
    cin >> n >> m >> k >> c;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
    		cin >> tree[i][j];
}

// 1단계 : 인접한 네 개의 칸 중 나무가 있는 칸의 수만큼 나무가 성장합니다.
void StepOne() {
    int dx[DIR_NUM] = {-1,  0, 1, 0};
    int dy[DIR_NUM] = { 0, -1, 0, 1};

    for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++) {
            if(tree[i][j] <= 0) continue;

            // 나무가 있는 칸의 수(cnt)만큼 나무가 성장합니다.
            int cnt = 0;
			for(int dir = 0; dir < 4; dir++) {
                int nx = i + dx[dir];
                int ny = j + dy[dir];
                if(IsOutRange(nx, ny)) continue;
                if(tree[nx][ny] > 0) cnt++;
            }
            tree[i][j] += cnt;
        }
}

// 2단계 : 기존에 있었던 나무들은 아무것도 없는 칸에 번식을 진행합니다.
void StepTwo() {
    int dx[DIR_NUM] = {-1,  0, 1, 0};
    int dy[DIR_NUM] = { 0, -1, 0, 1};

    // 모든 나무에서 동시에 일어나는 것을 구현하기 위해 하나의 배열을 더 이용합니다.
    // add_tree를 초기화해줍니다.
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++) 
            add_tree[i][j] = 0;

    for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++) {
            if(tree[i][j] <= 0) continue;

            // 해당 나무와 인접한 나무 중 아무도 없는 칸의 개수를 찾습니다.
            int cnt = 0;
            for(int dir = 0; dir < 4; dir++) {
                int nx = i + dx[dir];
                int ny = j + dy[dir];
                if(IsOutRange(nx, ny)) continue;
                if(herb[nx][ny]) continue;
                if(tree[nx][ny] == 0) cnt++;
            }

            // 인접한 나무 중 아무도 없는 칸은 cnt로 나눠준 만큼 번식합니다.
            for(int dir = 0; dir < 4; dir++) {
                int nx = i + dx[dir];
                int ny = j + dy[dir];
                if(IsOutRange(nx, ny)) continue;
                if(herb[nx][ny]) continue;
                if(tree[nx][ny] == 0) add_tree[nx][ny] += tree[i][j] / cnt;
            }
        }
    
    // add_tree를 더해 번식을 동시에 진행시킵니다.
    for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++) tree[i][j] += add_tree[i][j];
}

// 3단계 : 가장 많이 박멸되는 칸에 제초제를 뿌립니다.
void StepThree() {
    int dx[DIR_NUM] = {-1,  1, 1, -1};
    int dy[DIR_NUM] = {-1, -1, 1,  1};

    int max_del = 0;
    int max_x = 1;
    int max_y = 1;

    for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++) {
            // 모든 칸에 대해 제초제를 뿌려봅니다. 각 칸에서 제초제를 뿌릴 시 박멸되는 나무의 그루 수를 계산하고,
            // 이 값이 최대가 되는 지점을 찾아줍니다.
            if(tree[i][j] <= 0) continue;
            int cnt = tree[i][j];
            for(int dir = 0; dir < 4; dir++) {
                int nx = i;
                int ny = j;
				for(int x = 1; x <= k; x++) {
                    nx = nx + dx[dir];
                    ny = ny + dy[dir];
                    if(IsOutRange(nx, ny)) break;
                    if(tree[nx][ny] <= 0) break;
                    cnt += tree[nx][ny];
                }
            }
            if(max_del < cnt) {
                max_del = cnt;
                max_x = i;
                max_y = j;
            }
        }

    ans += max_del;

    // 찾은 칸에 제초제를 뿌립니다.
    if(tree[max_x][max_y] > 0) {
        tree[max_x][max_y] = 0;
        herb[max_x][max_y] = c;
        for(int dir = 0; dir < 4; dir++) {
            int nx = max_x;
            int ny = max_y;
            for(int x = 1; x <= k; x++) {
                nx = nx + dx[dir];
                ny = ny + dy[dir];
                if(IsOutRange(nx, ny)) break;
                if(tree[nx][ny] < 0) break;
                if(tree[nx][ny] == 0) {
                    herb[nx][ny] = c;
                    break;
                }
                tree[nx][ny] = 0;
                herb[nx][ny] = c;
            }
        }
    }
}

// 제초제의 기간을 1년 감소시킵니다.
void DeleteHerb() {
    for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++) 
            if(herb[i][j] > 0) 
                herb[i][j] -= 1;
}

int main() {
    // 입력을 받는 등 초기 작업을 합니다.
    Init();

    for(int i = 1; i <= m; i++) {
        // 1단계 : 인접한 네 개의 칸 중 나무가 있는 칸의 수만큼 나무가 성장합니다.
        StepOne();

        // 2단계 : 기존에 있었던 나무들은 아무것도 없는 칸에 번식을 진행합니다.
        StepTwo();

        // 제초제의 기간을 1년 감소시킵니다.
        DeleteHerb();

        // 3단계 : 가장 많이 박멸되는 칸에 제초제를 뿌립니다.
        StepThree();
    }

    cout << ans;
    return 0;
}