예제: 미세먼지 안녕!
문제
미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다.
공기청정기는 항상 1번 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼지가 있고, (r, c)에 있는 미세먼지의 양은 Ar,c이다.
1초 동안 아래 적힌 일이 순서대로 일어난다.
- 미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다.
- (r, c)에 있는 미세먼지는 인접한 네 방향으로 확산된다.
- 인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다.
- 확산되는 양은 Ar,c/5이고 소수점은 버린다.
- (r, c)에 남은 미세먼지의 양은 Ar,c - (Ar,c/5)×(확산된 방향의 개수) 이다.
- 공기청정기가 작동한다.
- 공기청정기에서는 바람이 나온다.
- 위쪽 공기청정기의 바람은 반시계방향으로 순환하고, 아래쪽 공기청정기의 바람은 시계방향으로 순환한다.
- 바람이 불면 미세먼지가 바람의 방향대로 모두 한 칸씩 이동한다.
- 공기청정기에서 부는 바람은 미세먼지가 없는 바람이고, 공기청정기로 들어간 미세먼지는 모두 정화된다.
다음은 확산의 예시이다.
공기청정기의 바람은 다음과 같은 방향으로 순환한다.
방의 정보가 주어졌을 때, T초가 지난 후 구사과의 방에 남아있는 미세먼지의 양을 구해보자.
입력
첫째 줄에 R, C, T (6 ≤ R, C ≤ 50, 1 ≤ T ≤ 1,000) 가 주어진다.둘째 줄부터 R개의 줄에 Ar,c (-1 ≤ Ar,c ≤ 1,000)가 주어진다. 공기청정기가 설치된 곳은 Ar,c가 -1이고, 나머지 값은 미세먼지의 양이다. -1은 2번 위아래로 붙어져 있고, 가장 윗 행, 아랫 행과 두 칸이상 떨어져 있다.
출력
첫째 줄에 T초가 지난 후 구사과 방에 남아있는 미세먼지의 양을 출력한다.예제 입력
7 8 1 0 0 0 0 0 0 0 9 0 0 0 0 3 0 0 8 -1 0 5 0 0 0 22 0 -1 8 0 0 0 0 0 0 0 0 0 0 0 10 43 0 0 0 5 0 15 0 0 0 0 0 40 0 0 0 20 0예제 출력
188
풀이
문제의 이해는 간단하다.
- 미세먼지의 확산
- 공기의 순환
- T번 반복
을 해 주면 되나, 미세먼지를 확산할 때와 공기를 순환할 때 오류가 일어나기 쉽다.
언제나 말하지만 삼성 문제는 알고리즘의 난이도 보다도, 조건을 잘 캐치하고 실수가 절대 없어야만 맞을 수 있는 문제들 같다.
필자는 1번과 2번 과정의 함수를 아예 나누어서 실수를 하지 않도록 노력했다. 물론 한 번에 되지는 않았지만, 그래서 그런지 몇 번의 디버깅을 통해 문제를 풀 수 있었다.
전체적인 소스코드는 아래와 같다.
소스 코드
#include<iostream>
#include<vector>
using namespace std;
int R, C, T;
int map[50][50];
int dir[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; //상, 하, 좌, 우
vector<int> air;
//먼지의 순환
void spreadDust() {
int spread[50][50] = { 0 };
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
//먼지가 있는 지점
if (map[r][c] > 0) {
int transDust = map[r][c] / 5;
//네 방향으로 확산
for (int i = 0; i < 4; i++) {
int dr = r + dir[i][0];
int dc = c + dir[i][1];
//공기청정기가 없거나 맵 안에 있는 경우만
if (dr >= 0 && dr < R && dc >= 0 && dc < C && map[dr][dc] != -1) {
spread[dr][dc] += transDust;
spread[r][c] -= transDust;
//map[dr][dc] += transDust;
//map[r][c] -= transDust;
}
}
}
}
}
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
map[r][c] += spread[r][c];
}
}
}
//공기 청정
void circling() {
int ar;
vector<pair<int, int>> pts;
//상
ar = air[0];
for (int r = ar - 1; r >= 0; r--) {
pts.push_back(make_pair(r, 0));
}
for (int c = 0; c < C; c++) {
pts.push_back(make_pair(0, c));
}
for (int r = 0; r <= ar; r++) {
pts.push_back(make_pair(r, C - 1));
}
for (int c = C - 1; c > 0; c--) {
pts.push_back(make_pair(ar, c));
}
for (int i = 0; i < pts.size() - 1; i++) {
map[pts[i].first][pts[i].second] = map[pts[i + 1].first][pts[i + 1].second];
}
map[pts[pts.size() - 1].first][pts[pts.size() - 1].second] = 0;
pts.clear();
//하
ar = air[1];
for (int r = ar + 1; r < R; r++) {
pts.push_back(make_pair(r, 0));
}
for (int c = 0; c < C; c++) {
pts.push_back(make_pair(R - 1, c));
}
for (int r = R - 1; r >= ar; r--) {
pts.push_back(make_pair(r, C - 1));
}
for (int c = C - 1; c >= 1; c--) {
pts.push_back(make_pair(ar, c));
}
for (int i = 0; i < pts.size() - 1; i++) {
map[pts[i].first][pts[i].second] = map[pts[i + 1].first][pts[i + 1].second];
}
map[pts[pts.size() - 1].first][pts[pts.size() - 1].second] = 0;
}
int resDust() {
for (int i = 0; i < T; i++) {
spreadDust(); //먼지의 순환
circling(); //공기 청정
}
int res = 0;
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
if (map[r][c] > 0)
res += map[r][c];
}
}
return res;
}
int main() {
cin >> R >> C >> T;
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
cin >> map[r][c];
if (map[r][c] == -1)
air.push_back(r);
}
}
cout << resDust() << endl;
return 0;
}풀이 후기
풀기 전에 손으로 조건들과 내가 시도할 로직을 정리하고 푸니, 큰 실수없이 풀 수 있었다. 앞으로도 이런 자세 유지하자.
그런데.. 삼성 기출문제도 좋은데 알고리즘 문제해결전략 도서를 안쳐다본지 근 한달이 되어간다. 내일은 기필코 보리라..
