백준 17144 미세먼지 안녕!
https://www.acmicpc.net/problem/17144
17144번: 미세먼지 안녕!
미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사
www.acmicpc.net
- 단순 구현 문제이다. 이런 문제는 무조건 맞춰야 코딩테스트 합격이 가능하다고 생각. 푸는데 50분정도가 걸렸다.
- 삼성 기출문제들은 시간복잡도를 계산하는게 무의미한 것 같다. 굳이 계산하면 모든 좌표에 대해 rxc만큼의 spread 연산을 진행하고, 이 후 약 2r+2c만큼 추가 연산을 진행하고.. 이 과정들을 t번 반복하기 때문에 O(rct)이다.
- 가장 먼저 모든 좌표에 대해서 미세먼지 확산을 시키고, 그 결과를 temp_spread 배열에 저장한다. 그 후, 공기청정기를 작동시켜서 미세먼지들을 한 칸씩 이동시킨다. 이 과정을 t번 반복한 후, 모든 미세먼지의 합을 구하면 된다.
- 이 문제의 핵심은 미세먼지의 이동 부분이라고 생각한다. 이 부분은 for문을 활용해서 사각형 테두리를 단방향으로 한 칸씩 잘 옮기는 것이 중요하다. 실제로 구현을 해보면, 굉장히 헷갈리는 것을 알 수 있다. 그래서 공식처럼 계속 보다보면 눈에 익어서 쉬워질 것이라는 생각이 든다. 필자의 경우 하나의 배열에서 값의 이동을 구현하지 않고, 동일한 배열을 하나 더 만들어서 그 배열에 한 칸 이동한 값들을 대입하는 식으로 구현을 했다.
#include <iostream>
#include <cstring>
using namespace std;
int r, c, t;
int arr[50][50];
int temp_spread[50][50];
int temp_cleaner[50][50];
int dx[] = { 0,0,1,-1 };
int dy[] = { -1,1,0,0 };
void run_cleaner(int air_cleaner_head) {
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
temp_cleaner[i][j] = temp_spread[i][j];
}
}
// 공기청청기 윗부분 작동
for (int i = 1; i < c-1; i++)
temp_cleaner[air_cleaner_head][i + 1] = temp_spread[air_cleaner_head][i];
for (int i = air_cleaner_head; i > 0; i--)
temp_cleaner[i - 1][c - 1] = temp_spread[i][c - 1];
for (int i = c - 1; i > 0; i--)
temp_cleaner[0][i - 1] = temp_spread[0][i];
for (int i = 0; i < air_cleaner_head-1; i++)
temp_cleaner[i + 1][0] = temp_spread[i][0];
temp_cleaner[air_cleaner_head][1] = 0;
// 공기청청기 아랫부분 작동
for (int i = 1; i < c - 1; i++)
temp_cleaner[air_cleaner_head+1][i + 1] = temp_spread[air_cleaner_head+1][i];
for (int i = air_cleaner_head+1; i < r-1; i++)
temp_cleaner[i + 1][c - 1] = temp_spread[i][c - 1];
for (int i = c - 1; i > 0; i--)
temp_cleaner[r-1][i - 1] = temp_spread[r-1][i];
for (int i = r-1; i > air_cleaner_head+1; i--)
temp_cleaner[i -1][0] = temp_spread[i][0];
temp_cleaner[air_cleaner_head+1][1] = 0;
}
void spread(int x, int y) {
int spread_num = 0;
int spread_volume = arr[x][y] / 5;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
if (arr[nx][ny] == -1) continue; // 공기청정기
spread_num++;
temp_spread[nx][ny] += spread_volume;
}
temp_spread[x][y] += arr[x][y] - (spread_num * spread_volume);
}
int main() {
int air_cleaner_head = 0;
cin >> r >> c >> t;
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
cin >> arr[i][j];
if (!air_cleaner_head && arr[i][j] == -1) air_cleaner_head = i;
}
}
while (t--) {
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if(arr[i][j] && arr[i][j] != -1) spread(i, j);
}
}
run_cleaner(air_cleaner_head);
// 공기청정기 가동 이후 상태에 공기청정기 좌표값 추가
temp_cleaner[air_cleaner_head][0] = -1;
temp_cleaner[air_cleaner_head + 1][0] = -1;
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
arr[i][j] = temp_cleaner[i][j];
}
}
memset(temp_spread, 0, sizeof(temp_spread));
memset(temp_spread, 0, sizeof(temp_cleaner));
}
int answer = 0;
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (arr[i][j] && arr[i][j] != -1) answer += arr[i][j];
}
}
cout << answer;
return 0;
}