[코드트리] 나무박멸 (C++)

[문제]

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

코드트리

[풀이]

 

삼성전자 22년 상반기 SW 역량테스트 오후 2번 문제

 

1. 인접한 4개의 칸에 나무의 개수만큼 성장

2. 인접한 4개의 칸에 벽.다른 나무.제초제가 없는 칸에 대해 번식 진행

3. 나무가 가장 많이 박멸되는 곳에 제초제 뿌림

   - 벽 또는 나무가 없는 칸의 경우 그 이후 칸에는 제초제를 전파하지 못함

   - 이러한 칸이 여러개면 행이 작은 칸에 , 행이 같으면 열이 더 작은 칸에 제초제를 뿌린다.

 

각 스텝별로 api를 만들었다.

 

먼저 1번의 경우  growthTree에서 처리해줬다. 현재 나무가 존재하는 칸에 대해 인접한 칸의 나무가 존재하는 칸의 개수만큼 성장하도록 구현

 

2번의 경우 breedTree에서 조건문을 통해 제초제. 다른 나무. 벽의 존재 여부를 확인 후 없다면 번식을 진행하도록 구현해줬다.

 

그 다음으로 제초제는 매년 1씩 감소하므로 deleteHerb에서 제초제가 존재하는 칸에 대해 -1씩 해주었다.

 

마지막으로  dieTree에서 3번을 처리해주었다. 제초제를 뿌릴 수 있는 모든 칸에 대해 확인해주었다.

각 칸 마다 박멸하는 나무의 개수.행.열을 벡터에 저장하여 comp 함수를 통해 정렬을 해주었다.

 

또한 map에서는 나무가 없는 빈 칸과 제초제가 뿌려진 곳을 모두 0으로 처리하여 따로 구분해주지 않았다.

제초제가 뿌려진 곳은 herb 배열의 0이 아닌 칸이 되므로 빈칸과 제초제가 뿌려진 칸을 비교할 수 있다.

 

[코드]

//m년 동안 총 박멸한 나무의 그루 수를 구하는 프로그램을 작성해보세요

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

#define MAX 20

using namespace std;

struct info{
    int cnt,x,y;
};

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

int N,M,K,C;
int map[MAX][MAX]={0,};
int herbicide[MAX][MAX]={0,};
int res =0;

bool comp( info a, info b)
{
    if(a.cnt > b.cnt )  return true;
    else if(a.cnt < b.cnt )  return false;

    if(a.x < b.x )  return true;
    else if(a.x > b.x )  return false;

    if(a.y < b.y )  return true;
    return false;
}

void growthTree()
{
    int addTree[MAX][MAX]={0,};
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(map[i][j] <= 0)  continue;
            int cnt =0;
            for(int k=0;k<8;k+=2){
                int nx = i + dx[k];
                int ny = j + dy[k];

                if( nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
                if( map[nx][ny] <= 0)   continue;
                cnt++;
            }
            addTree[i][j]=cnt;
        }
    }

    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            map[i][j] += addTree[i][j];
        }
    }
}

void breedTree()
{
    int addTree[MAX][MAX]={0,};

    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(map[i][j] <= 0)  continue;
            int cnt =0;
            for(int k=0;k<8;k+=2){
                int nx = i + dx[k];
                int ny = j + dy[k];

                if( nx < 0 || ny < 0 || nx >= N || ny >= N || map[nx][ny] != 0 || herbicide[nx][ny] != 0) continue;
                
                cnt++;
            }
            for(int k=0;k<8;k+=2){
                int nx = i + dx[k];
                int ny = j + dy[k];

                if( nx < 0 || ny < 0 || nx >= N || ny >= N || map[nx][ny] != 0 || herbicide[nx][ny] != 0) continue;
                addTree[nx][ny]+=map[i][j]/cnt;
            }
        }
    }

    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            map[i][j] += addTree[i][j];
        }
    }
}

void dieTree()
{
    vector<info> die;

    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if( map[i][j] <= 0)  continue;
            int cnt = map[i][j];
            for(int d=1;d<8;d+=2){
                for(int l=1;l<=K;l++){
                    int nx = i + dx[d]*l;
                    int ny = j + dy[d]*l;
                    if( nx < 0 || ny < 0 || nx >= N || ny >= N || map[nx][ny] <= 0) break;
                    cnt += map[nx][ny];
                }
            }
            if(cnt > 0)   die.push_back({cnt,i,j});
        }
    }
    

    
    if( die.size() == 0)    return ;
    sort(die.begin(), die.end(),comp);
    res += die[0].cnt;
    int x =die[0].x;
    int y =die[0].y;
    
    if( map[x][y] > 0){
        map[x][y] = 0;
        herbicide[x][y] = C;

        for(int d=1;d<8;d+=2){
            for(int l=1;l<=K;l++){
                int nx = x + dx[d]*l;
                int ny = y + dy[d]*l;
                if( nx < 0 || ny < 0 || nx >= N || ny >= N || map[nx][ny] <0 ) break;
                
                herbicide[nx][ny] = C;
                
                if( map[nx][ny] == 0 ){
                    break;
                } else {
                    map[nx][ny] = 0;
                }
            }
        }
    }
    
}

void deleteHerb()
{
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(herbicide[i][j] == 0)    continue;
            herbicide[i][j]-=1;
        }
    }
}

int main(void)
{
    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 i=0;i<M;i++){
        growthTree();
        breedTree();
        deleteHerb();
        dieTree();
    }
    cout << res;
    return 0;
}