191015 백준 알고리즘 문제풀기
15 Oct 2019 | baekjoon[16235] 나무 재테크
- 난이도: 상
- 문제 이해 30분, 구현하는데 40분, 디버깅 1시간정도 걸렸다.
- 결국 시간 복잡도때문에 틀렸다.
- 아무래도 우선순위 큐를 사용하다보니 늦어졌고, 게다가 이중 for문으로 하나하나 좌표단위로 접근하다보니 틀린듯 하다.
- 모든 문제는 풀기에 앞서 정확하게 조건을 이해하고, 정리하고, 직접 어떻게 되는지 손으로 풀어보고 이해한다음에 풀기 시작하면 못 풀 문제는 없을것이라 생각한다..
- 하지만 맞게 풀었다고 무조건 맞는것도 아닌듯하다 ㅠㅠ
- 시간복잡도..
- 만약 시험에 나왔으면 시간복잡도때문에 틀렸다.
- 문제
- https://www.acmicpc.net/problem/16235
- 정사각형 맵의 크기 N, 나무의 개수 M, 햇수 K가 순서대로 입력됨
- 다음으로, 각 맵에 매 해 겨울 줄 비료상태가 입력됨
- 마지막으로 M개의 나무 좌표와 나무 나이가 입력 됨
- 조건
- 한 칸에는 여러개의 나무가 존재 할 수 있다.
- 이게 핵심 조건
- 가장 처음 땅에 있는 양분은 모두 5다.
- 봄에는
- 자신 나이만큼 나무가 양분을 먹고 나이가 1 증가한다.
- 자신이 존재하는 칸의 양분만 섭취 가능하다.
- 한 칸에 여러 나무가 존재시, 나이 어린 나무부터 양분을 섭취한다.
- 만약 땅에 양분이 부족해 나이만큼 양분을 먹지 못하면 즉시 사망한다.
- 여름에는
- 봄에 죽은 나무가 양분이 된다.
- 양분이 되는 죽은 나무는 나이를 2로 나눈 값이 해당 칸의 양분으로 더해진다.(소숫점 버림)
- 가을에는
- 나무가 번식한다.
- 나이가 5의 배수일 때만 번식한다.
- 땅 범위를 벗어나는 번식은 하지 않는다.
- 인접한 8개 칸에 나이 1인 나무가 새로 생성된다.
- 겨울에는
- 땅에 로봇이 양분을 추가한다.
- 추가되는 양분은 위에서 비료상태로 입력된다.
- 한 칸에는 여러개의 나무가 존재 할 수 있다.
- 풀이
- 우선순위 큐 이용
- 우선순위 큐는 큐에 새로 입력되는 데이터가 어떠한 정렬 순서에 따라 정렬되어 자기 자리를 찾아간다.
- C++ STL에서는
<queue>
에서 제공된다.priority_queue<data_type, container<data_type>, order<data_type>> pq_name
- ex.
priority_queue<int, vector<int>, greater<int>> pq
greater
규칙을 따르면 가장 작은 값이pq.top()
에 존재한다.- 반대로
less
규칙을 따르면 가장 큰 값이pq.top()
에 존재한다.
- ex.
- 우선순위 큐를 2차원 배열 형태로 이용한다면 시간초과로 문제가 틀린다.
- 아래 코드는 틀린 문제 풀이 코드(정답은 맞지만 시간조건을 초과함)
- 다양한 방법으로 for문을 최소화해봤지만 소용없다.
- 우선순위 큐 이용
#pragma warning(disable:4996)
#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
int biryo[11][11];
int dead[11][11];
int curmap[11][11];
int dx[] = { 0,1,1,1,0,-1,-1,-1 };
int dy[] = { -1,-1,0,1,1,1,0,-1 };
priority_queue<int, vector<int>, greater<int>> c_tree[11][11]; // 작은게 맨 위로
priority_queue<int, vector<int>, greater<int>> n_tree[11][11];
void init_curmap(int N)
{
for (int j = 1; j <= N; j++)
{
for (int i = 1; i <= N; i++)
{
curmap[j][i] = 5;
}
}
}
int main()
{
int N, M, K;
scanf("%d %d %d", &N, &M, &K);
//비료맵 저장
for (int j = 1; j <= N; j++)
{
for (int i = 1; i <= N; i++)
{
scanf("%d", &biryo[i][j]);
}
}
//나무 저장
for (int i = 0; i < M; i++)
{
int x, y, z;
scanf("%d %d %d", &x, &y, &z);
c_tree[y][x].push(z);
} // c_tree에는 해당 좌표에 나무 크기가 순서대로 저장됨
int year = K;
// 맵 초기화
init_curmap(N);
while (year--)
{//년수동안
//봄
for (int j = 1; j <= N; j++)
{
for (int i = 1; i <= N; i++)
{
if (c_tree[j][i].size() != 0)
{// 현재 위치 나무가 존재한다면
while (!c_tree[j][i].empty())
{//현재 위치 나무들동안 나이가 어린 나무부터
int cur_size = c_tree[j][i].top();
c_tree[j][i].pop(); // 현재 나무를 뽑아서
if (curmap[j][i] >= cur_size)
{//만약 해당 위치 양분이 현재 나이보다 많다면
curmap[j][i] -= cur_size; // 양분 먹고
n_tree[j][i].push(cur_size + 1); // 나이 1 증가해서 다음 맵에저장
continue;
}
else
{//해당 위치 양분이 나이보다 부족하다면
dead[j][i] += int(cur_size / 2); // 죽은 나무가 되어 반 크기의 양분이 됨
}
}
}
//여름, 겨울 비료주기
curmap[j][i] += dead[j][i];
curmap[j][i] += biryo[j][i];
dead[j][i] = 0; // dead 초기화
}
}
////여름, 겨울(비료 주기)
//for (int j = 1; j <= N; j++)
//{
// for (int i = 1; i <= N; i++)
// {
// //죽은 나무는 양분이 된다.
// curmap[j][i] += dead[j][i];
// curmap[j][i] += biryo[j][i];
// dead[j][i] = 0; // dead 초기화
// }
//}
//가을 (나무 번식)
for (int j = 1; j <= N; j++)
{
for (int i = 1; i <= N; i++)
{
if (n_tree[j][i].size() != 0)
{// 만약 현재위치 나무가 존재한다면
while (!n_tree[j][i].empty())
{// 현재위치 나무들동안
int cur_size = n_tree[j][i].top(); // 현재 나무 크기 저장
n_tree[j][i].pop(); // 현재 나무 뽑고
if (cur_size % 5 == 0)
{//만약 현재 나무가 번식조건이라면(5의 배수)
for (int k = 0; k < 8; k++)
{
int nx = i + dx[k]; // 다음위치 찾고
int ny = j + dy[k];
if (nx < 1 || N < nx||ny < 1 || N < ny) continue; // 범위 안이라면
c_tree[ny][nx].push(1); // 현재 맵의 다음 위치에 번식
}
c_tree[j][i].push(cur_size); // 현재 맵에 현재 나무 옮겨심기
}
else
{//만약 나무가 번식조건이 아니라면
c_tree[j][i].push(cur_size); // 다음 맵에 나무를 옮겨심는다
}
}
}
}
}
//겨울 비료주기는 여름에
}
// 나무 개수 세기
int cnt = 0;
for (int j = 1; j <= N; j++)
{
for (int i = 1; i <= N; i++)
{
if (c_tree[j][i].size() != 0)
{//나무 있으면
while (!c_tree[j][i].empty())
{//나무들을
c_tree[j][i].pop();//뽑고
cnt++; //센다.
}
}
}
}
printf("%d\n", cnt);
//std::system("pause");
return 0;
}
- 이 문제를 덱을 이용해서 풀면 다음과 같다
- 덱을 이용하면 시간초과 문제를 해결 할 수 있고(sorting 없으니까) 문제를 통과할 수 있다.
- 문제에서 입력으로 주어지는 나무의 위치는 모두 서로 다름 조건을 잘 고민해보면 덱으로 풀 수 있는 문제라는 힌트를 얻을 수 있었다.
- 문제를 꼼꼼히 읽는게 최고의 방법인듯 하다.
- 덱은 앞에서 자료를 넣고 빼고, 뒤에서 넣고 빼고 할 수 있다.
- 위 코드에서 우선순위 큐를 덱으로만 바꾸고 중간에 코드 살짝만 바꾸면 된다.
- 어떠한 좌표에서 나무 나이가 작은 값이 맨 오른쪽으로, 큰 값이 맨 왼쪽으로 가야한다.
- 덱에서 새로 생성되는 나무들은 무조근 크기가 작으니까
push_back
으로 넣으면 된다. - 2 개의 덱을 번갈아가며 사용하기 때문에, 새로 생성되는 나무는 무조건 오른쪽(back)에서 넣고, 기존 나무는 왼쪽(front)에서 넣으면 순서는 항상 바뀔 수 없다.
- pop은 무조건 back에서만, push는 새 나무는 back, 큰 나무는 front에서 push!
- 이 순서만 지키면 무조건 순서는 정렬되어있게 된다.
- 자세한건 밑에 코드 참조
#pragma warning(disable:4996)
#include <iostream>
#include <cstdio>
#include <queue>
#include <deque>
using namespace std;
int biryo[11][11];
int dead[11][11];
int curmap[11][11];
int dx[] = { 0,1,1,1,0,-1,-1,-1 };
int dy[] = { -1,-1,0,1,1,1,0,-1 };
deque<int> c_tree[11][11];
deque<int> n_tree[11][11];
int main()
{
int N, M, K;
scanf("%d %d %d", &N, &M, &K);
//비료맵 저장
for (int j = 1; j <= N; j++)
{
for (int i = 1; i <= N; i++)
{
scanf("%d", &biryo[i][j]);
curmap[j][i] = 5; // 처음 비료 초기화
}
}
//나무 저장
for (int i = 0; i < M; i++)
{
int x, y, z;
scanf("%d %d %d", &x, &y, &z);
c_tree[y][x].push_front(z); // 일단은 그냥 순서 상관없이 집어넣는다. 어차피 입력되는 나무의 위치는 모두 다르니까.
} // c_tree에는 해당 좌표에 나무 크기가 저장
int year = K;
while (year--)
{//년수동안
//봄
for (int j = 1; j <= N; j++)
{
for (int i = 1; i <= N; i++)
{
if (c_tree[j][i].size() != 0)
{// 현재 위치 나무가 존재한다면
while (!c_tree[j][i].empty())
{//현재 위치 나무들동안
int cur_size = c_tree[j][i].back(); // 뒤쪽에서 어린 나무부터 뽑아낸다.
c_tree[j][i].pop_back();
if (curmap[j][i] >= cur_size)
{//만약 해당 위치 양분이 현재 나이보다 많다면
curmap[j][i] -= cur_size; // 양분 먹고
n_tree[j][i].push_front(cur_size + 1); // 나이 1 증가해서 다음 맵에 앞으로 집어넣는다.
continue;
}
else
{//해당 위치 양분이 나이보다 부족하다면
dead[j][i] += int(cur_size / 2); // 죽은 나무가 되어 반 크기의 양분이 됨
}
}
}
//여름, 겨울 비료주기
curmap[j][i] += dead[j][i];
curmap[j][i] += biryo[j][i];
dead[j][i] = 0; // dead 초기화
}
}
//가을 (나무 번식)
for (int j = 1; j <= N; j++)
{
for (int i = 1; i <= N; i++)
{
if (n_tree[j][i].size() != 0)
{// 만약 현재위치 나무가 존재한다면
while (!n_tree[j][i].empty())
{// 현재위치 나무들동안
int cur_size = n_tree[j][i].back(); // 가장 작은 나무부터
n_tree[j][i].pop_back(); // 현재 나무 뽑고
if (cur_size % 5 == 0)
{//만약 현재 나무가 번식조건이라면(5의 배수)
for (int k = 0; k < 8; k++)
{
int nx = i + dx[k]; // 다음위치 찾고
int ny = j + dy[k];
if (nx < 1 || N < nx || ny < 1 || N < ny) continue; // 범위 안이라면
c_tree[ny][nx].push_back(1); // 현재 맵의 다음 위치에 번식
}// 나무 번식은 무조건 제일 작은 나무 크기이므로 덱의 뒤에서 집어넣는다.
c_tree[j][i].push_front(cur_size); // 현재 맵에 현재 나무 옮겨심기
}// 현재 나무는 무조건 큰 나무일 것이므로 덱 앞에 집어넣는다.
else
{//만약 나무가 번식조건이 아니라면
c_tree[j][i].push_front(cur_size); // 그냥 다음 맵에 나무를 옮겨심는다(앞으로 넣어야 함)
}
}
}
}
}
//겨울 비료주기는 여름에 완료
}
// 나무 개수 세기
int cnt = 0;
for (int j = 1; j <= N; j++)
{
for (int i = 1; i <= N; i++)
{
cnt += c_tree[j][i].size(); // 해당 위치 사이즈가 곧 나무 갯수이므로
}
}
printf("%d\n", cnt);
//std::system("pause");
return 0;
}
- 쉬운줄 알고 덤벼보면 문제는 꼭 항상 어렵다.