문제 이해 단계
https://www.acmicpc.net/problem/16235
NxN 크기에 땅에 M개의 나무를 심는다.
나무에는 (x, y) 좌표 정보와 나이가 정보가 존재한다.
그리고 2차원 맵에 각각의 칸에는 양분이라는 정보들이 존재한다.
결과적으로 구해야 하는 것은 K 년 이후에 살아있는 나무의 개수인데,
1년은 4계절로 이루어져 있다. 그리고 계절마다 수행해야 하는 기능들이 존재한다.
봄
- 나무가 자신의 나이만큼 양분을 먹는다. 여러 개일 경우 나이가 작은 순으로 먼저 먹는다.
- 자신의 나이만큼 양분을 먹지 못할 경우, 양분을 먹지 않고 죽는다.
여름
- 봄에 죽은 나무들의 나이 절반이
- 해당 칸의 양분으로 들어간다.
가을
- 칸에 있는 나무가 5의 배수일 경우
- 인접한 8개의 칸에 나이가 1인 나무가 생긴다.
겨울
- 입력으로 주어진 양분 A [r][c]를 각 땅에 준다.
해당 행동을 K 년 했을 때의
살아남은 나무의 개수를 구하는 문제이다.
문제 접근 단계
NxN의 맵이 주어지고 인접한 칸에 대한 활동이 주어진다.
그리고 각 계절마다 해야 할 기능이 있다.
높은 확률로 구현 문제일 가능성이 높아 보인다.
그중에서도 시뮬레이션일 가능성이 높다.
딱히 기발한 아이디어나 그런 건 필요 없어 보이는데,
아마 문제에서 시키는 데로 차례대로 구현만 잘하면 될 것 같다.
일단 문제 조건부터 살펴보자.
NxN의 맵인데 최대 10x10까지 가능하다.
범위가 굉장히 작기 때문에 브루트포스로 충분하다.
즉, 어떤 식으로든 탐색이 가능하기 때문에 시간 복잡도는 크게 신경 안 써도 될 것 같다.
이 문제에서 핵심적으로 봐야 하는 부분은
같은 1x1 칸에 여러 개의 나무가 심어져 있을 수 있다는 것이다.
즉, 2차원 맵을 만들 때,
한 공간에 여러 개의 나무가 들어갈 수 있다는 것도 명심해둬야 한다는 것이다.
그래서 나는 int형이나 그런 것이 아닌 여러 개를 담기 위해 vector 컨테이너를 사용하였다.
그다음으로 생각했던 것은 봄에서 여름으로 넘어갈 때다.
여름에 있는 기능 중에서 봄에서 죽은 나무들이 양분으로 변한다는 것이 있었는데,
이는 봄에 죽은 나무들의 정보들을 저장해 둘 컨테이너가 필요하단 소리이다.
가을의 경우에는 bfs 하듯이 방향을 탐색하는 느낌을 하면 될 것이고,
겨울은 크게 신경 쓸 것이 없을 것 같다
시뮬레이션 문제인 만큼 나머지는 구현문제에서
코드로 중점적으로 다루는 것이 나아 보인다.
바로 문제 구현 단계로 넘어가 보자.
문제 구현 단계
// 나무의 정보를 담은 구조체
struct Tree{
int x;
int y;
int val; // 나이
};
int N,M;
vector<int> map[11][11]; // 맵
int cnt[11][11] = {0,}; // 현재 남아있는 양분
int grows[11][11] = {0,}; // 입력으로 주어진 양분
vector<Tree> dead; // 죽은 나무
// 봄 활동
void spring(){
for(int i = 1; i <= N; i++){
for(int j = 1; j<= N; j++){
// 어린 나무부터 영양을 주기 위한 정렬
sort(map[i][j].begin(),map[i][j].end());
for(int k = 0; k < map[i][j].size(); k++){
// 양분이 나이보다 크거나 같을 때(양분을 받을 수 있을 때만)
if(cnt[i][j] - map[i][j][k] >= 0) {
cnt[i][j] -= map[i][j][k];
map[i][j][k]++;
}
else{
// 받을수 없을 때
dead.push_back({i,j,map[i][j][k]});
// 맵 칸에서 지움
map[i][j].erase(map[i][j].begin()+k);
k--;
}
}
}
}
}
// 여름 활동
void summer(){
for(int i = 0; i < dead.size(); i++){
int x = dead[i].x;
int y = dead[i].y;
int val = dead[i].val;
// 죽은 나무 나이/2 만큼 양분 채움
cnt[x][y] += (val/2);
}
}양분을 먹는 spring 함수와, 죽은 나무들을 양분으로 돌리는 summer 함수이다.
일단 나무의 정보를 한 군데 모아두기 위해
Tree라는 구조체로 좌표 정보와 나이 정보를 한 군데에 모아뒀다.
이는 나중에 죽은 나무들을 모아둘 때 한 번에 정보를 모아두기 위함이다.
전역변수들을 설명하면
cnt는 현재 남아있는 양분의 정보, grow는 입력으로 받은 양분의 정보이다.
나머지는 주석으로 달아놨으니 크게 헷갈릴 것은 없을 것이라 생각한다.
spring 함수에서는 전체 2차원 맵을 탐색 하면서 나무가 있는 맵을 찾는다.
중간에 오름차순 정렬을 해주는 이유는
여러 개일 경우 어린 나무부터 양분을 주기 위해서이다.
정렬 후 연산을 통해 양분을 받을 수 있는 경우에만 양분을 받고,
그렇지 않은 경우에는 해당 맵 벡터에서 제거하고 죽은 나무 dead 벡터에 추가한다.
이는 나중에 summer 함수에서 나이/2 만큼 해당 칸의 양분으로 되돌린다.
// 인접한 8칸으로 나무를 생성
void spreadTree(int x, int y){
// 8방향
int dx[] = {0,0,-1,1,-1,-1,1,1};
int dy[] = {-1,1,0,0,-1,1,-1,1};
for(int i = 0; i < 8; i++){
int nx = x+ dx[i];
int ny = y+ dy[i];
if(nx < 1 || ny < 1 || nx > N || ny > N) continue;
map[nx][ny].push_back(1); // 나이 1
}
}
// 가을
void fall(){
for(int i = 1; i <= N; i++){
for(int j = 1; j <= N; j++){
if(map[i][j].empty()) continue;
for(int k = 0; k < map[i][j].size(); k++){
// 배수가 5인 경우만
if(map[i][j][k] % 5 == 0) spreadTree(i,j);
}
}
}
}
// 겨울
void winter(){
for(int i = 1; i <= N; i++){
for(int j = 1; j <= N; j++){
// 입력 양분만큼 더하기
cnt[i][j] += grows[i][j];
}
}
}마지막으로 가을과 겨울을 나타내는 fall과 winter 함수이다.
크게 볼 것은 spreadTree함수인데,
단순히 8개의 인접한 칸으로 나무를 생성하는 것이다.
매개변수로 시작할 위치를 받는다.
BFS와 비슷하게 방향을 설정하고 범위를 체크한다.
이후에 해당 방향에 1을 추가하는데, 1인 이유는 나이가 1이어야 하기 때문이다.
fall 함수에서 배수가 5인 경우에만 이 함수가 작동하도록 한다.
winter 함수에는 입력으로 받아둔 grows를 cnt에 더한다.
이게 모든 설명의 끝이고 이제 아래에 전체 코드를 올려두고 끝내겠다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 나무의 정보를 담은 구조체
struct Tree{
int x;
int y;
int val; // 나이
};
int N,M;
vector<int> map[11][11]; // 맵
int cnt[11][11] = {0,}; // 현재 남아있는 양분
int grows[11][11] = {0,}; // 입력으로 주어진 양분
vector<Tree> dead; // 죽은 나무
// 봄 활동
void spring(){
for(int i = 1; i <= N; i++){
for(int j = 1; j<= N; j++){
// 어린 나무부터 영양을 주기 위한 정렬
sort(map[i][j].begin(),map[i][j].end());
for(int k = 0; k < map[i][j].size(); k++){
// 양분이 나이보다 크거나 같을 때(양분을 받을 수 있을 때만)
if(cnt[i][j] - map[i][j][k] >= 0) {
cnt[i][j] -= map[i][j][k];
map[i][j][k]++;
}
else{
// 받을수 없을 때
dead.push_back({i,j,map[i][j][k]});
// 맵 칸에서 지움
map[i][j].erase(map[i][j].begin()+k);
k--;
}
}
}
}
}
// 여름 활동
void summer(){
for(int i = 0; i < dead.size(); i++){
int x = dead[i].x;
int y = dead[i].y;
int val = dead[i].val;
// 죽은 나무 나이/2 만큼 양분 채움
cnt[x][y] += (val/2);
}
}
// 인접한 8칸으로 나무를 생성
void spreadTree(int x, int y){
// 8방향
int dx[] = {0,0,-1,1,-1,-1,1,1};
int dy[] = {-1,1,0,0,-1,1,-1,1};
for(int i = 0; i < 8; i++){
int nx = x+ dx[i];
int ny = y+ dy[i];
if(nx < 1 || ny < 1 || nx > N || ny > N) continue;
map[nx][ny].push_back(1); // 나이 1
}
}
// 가을
void fall(){
for(int i = 1; i <= N; i++){
for(int j = 1; j <= N; j++){
if(map[i][j].empty()) continue;
for(int k = 0; k < map[i][j].size(); k++){
// 배수가 5인 경우만
if(map[i][j][k] % 5 == 0) spreadTree(i,j);
}
}
}
}
// 겨울
void winter(){
for(int i = 1; i <= N; i++){
for(int j = 1; j <= N; j++){
// 입력 양분만큼 더하기
cnt[i][j] += grows[i][j];
}
}
}
int main(){
int K;
scanf("%d %d %d",&N,&M,&K);
for(int i = 1; i <= N; i++){
for(int j = 1; j <= N; j++) cin >> grows[i][j];
}
for(int i = 0; i < M; i++){
int v1,v2,v3;
cin >> v1 >> v2 >> v3;
map[v1][v2].push_back(v3);
}
fill(&cnt[0][0],&cnt[10][11],5);
while(K--){
dead.clear();
spring();
summer();
fall();
winter();
}
int ans = 0;
for(int i = 1; i <= N; i++){
for(int j = 1; j<= N; j++){
if(map[i][j].empty()) continue;
ans += map[i][j].size();
}
}
cout << ans;
}
시행착오
생각 외로 그렇게 어렵지 않게 푼 문제.
다른 것보다 구현 난이도가 그렇게 높지 않은 것 같은데..
다른 사람들은 최적화한다고 고생했다고 한다. 근데 난 C++이라서 그런가?
전혀 그런 게 없었고 그냥 시키는 대로 구현하다 보니 풀렸다.
BFS로 익숙한 구현을 하다 보니 2시간 내외로 풀 수 있었다.