이번에는 백준 17144번 미세먼지 안녕! 문제를 풀어보았습니다.
이 문제는 1초마다 일어나는 두 가지 변화를 순서대로 구현해야 합니다.
먼저 모든 미세먼지가 동시에 확산되고, 이후 위쪽 공기청정기는 반시계 방향으로, 아래쪽 공기청정기는 시계 방향으로 공기를 순환시킵니다.
각 과정을 함수로 나누어 구현하는 시뮬레이션 문제입니다.
문제 설명
R × C 크기의 격자에 미세먼지와 공기청정기가 존재합니다.
공기청정기는 첫 번째 열에 위아래로 두 칸을 차지하며, 매초 다음 과정이 순서대로 일어납니다.
- 미세먼지가 인접한 네 방향으로 동시에 확산됩니다.
- 위쪽 공기청정기는 반시계 방향으로 작동합니다.
- 아래쪽 공기청정기는 시계 방향으로 작동합니다.
이 과정을 T초 동안 반복한 뒤, 방에 남아 있는 미세먼지의 총량을 구하는 문제입니다.
풀이 아이디어
1초 동안 일어나는 상태 변화를 다음과 같이 나누어 구현하였습니다.
- 미세먼지 확산량 계산
- 계산된 확산량 반영
- 아래쪽 공기청정기 작동
- 위쪽 공기청정기 작동
- 다음 확산에 사용할 미세먼지 위치를 큐에 저장
미세먼지는 모든 칸에서 동시에 확산되어야 합니다.
따라서 한 칸에서 확산된 미세먼지를 바로 원본 배열에 더하면, 아직 확산하지 않은 칸의 미세먼지 양이 변하여 잘못된 결과가 발생할 수 있습니다.
이를 방지하기 위해 확산되는 미세먼지는 별도의 배열인
plus_data에 저장한 뒤, 모든 확산이 끝난 후 원본 배열에 한꺼번에 더하였습니다.
공기청정기의 작동은 순환 방향을 네 구간으로 나누어 직접 값을 이동시키는 방식으로 구현하였습니다.
코드
#include <bits/stdc++.h>
using namespace std;
int dy[4] = {-1, 1, 0, 0};
int dx[4] = {0, 0, 1, -1};
queue<pair<int, int>> q;
pair<int, int> puri[2];
int input_data[50][50];
int plus_data[50][50];
int R,C,T;
void flooding() {
while(!q.empty()){
auto[y,x] = q.front();
q.pop();
int each = input_data[y][x] / 5;
for (int i=0; i<4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny < 0 || ny >= R || nx < 0 || nx >= C) continue;
if ((puri[0].first == ny && puri[0].second == nx) || (puri[1].first == ny && puri[1].second == nx)) continue;
input_data[y][x] -= each;
plus_data[ny][nx] += each;
}
}
}
void clockly_puri() {
int y = puri[1].first;
// 왼쪽 벽: 아래에서 위로 이동
for (int r = y + 1; r < R - 1; r++) {
input_data[r][0] = input_data[r + 1][0];
}
// 아래쪽 행: 오른쪽에서 왼쪽으로 이동
for (int c = 0; c < C - 1; c++) {
input_data[R - 1][c] = input_data[R - 1][c + 1];
}
// 오른쪽 벽: 위에서 아래로 이동
for (int r = R - 1; r > y; r--) {
input_data[r][C - 1] = input_data[r - 1][C - 1];
}
// 공기청정기 행: 왼쪽에서 오른쪽으로 이동
for (int c = C - 1; c > 1; c--) {
input_data[y][c] = input_data[y][c - 1];
}
input_data[y][1] = 0;
}
void antiClockly_puri() {
int y = puri[0].first;
// 왼쪽 벽: 위에서 아래로 이동
for (int r = y - 1; r >= 1; r--) {
input_data[r][0] = input_data[r - 1][0];
}
// 위쪽 행: 오른쪽에서 왼쪽으로 이동
for (int c = 0; c < C - 1; c++) {
input_data[0][c] = input_data[0][c + 1];
}
// 오른쪽 벽: 아래에서 위로 이동
for (int r = 0; r < y; r++) {
input_data[r][C - 1] = input_data[r + 1][C - 1];
}
// 공기청정기 행: 왼쪽에서 오른쪽으로 이동
for (int c = C - 1; c > 1; c--) {
input_data[y][c] = input_data[y][c - 1];
}
input_data[y][1] = 0;
}
void plus_flooding() {
for (int i=0; i<R; i++) {
for (int j=0; j<C; j++) {
if (i == puri[0].first && j == puri[0].second) continue;
if (i == puri[1].first && j == puri[1].second) continue;
input_data[i][j] += plus_data[i][j];
}
}
}
void add_queue() {
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
if (input_data[r][c] > 0) {
q.push({r, c});
}
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> R >> C >> T;
int puri_num=0;
for (int i=0; i<R; i++) {
for (int j=0; j<C; j++) {
cin >> input_data[i][j];
if (input_data[i][j] > 0) q.push({i,j});
if (input_data[i][j] == -1) puri[puri_num++] = {i,j};
}
}
for (int i=0; i<T; i++) {
memset(plus_data, 0, sizeof(plus_data));
flooding();
plus_flooding();
clockly_puri();
antiClockly_puri();
add_queue();
}
int ret = 0;
for (int i=0; i<R; i++) {
for (int j=0; j<C; j++) {
if (i == puri[0].first && j == puri[0].second) continue;
if (i == puri[1].first && j == puri[1].second) continue;
ret += input_data[i][j];
}
}
cout << ret;
return 0;
}풀이 흐름
-
방의 상태와 공기청정기의 위치를 입력받습니다.
-
미세먼지가 있는 좌표를 큐에 저장합니다.
-
매초
plus_data배열을 0으로 초기화합니다. -
큐에 저장된 미세먼지를 네 방향으로 확산시킵니다.
-
각 칸으로 확산된 미세먼지를
plus_data에 저장합니다. -
모든 확산이 끝난 뒤
plus_data의 값을input_data에 더합니다. -
아래쪽 공기청정기를 시계 방향으로 작동시킵니다.
-
위쪽 공기청정기를 반시계 방향으로 작동시킵니다.
-
현재 남아 있는 미세먼지 좌표를 다시 큐에 저장합니다.
-
위 과정을
T초 동안 반복한 뒤 모든 미세먼지의 양을 더해 출력합니다.
구현 포인트
1. 공기청정기 위치 저장
pair<int, int> puri[2];공기청정기는 첫 번째 열에 위아래로 붙어 있습니다.
입력을 위에서 아래로 받기 때문에
puri[0] = 위쪽 공기청정기
puri[1] = 아래쪽 공기청정기가 됩니다.
if (input_data[i][j] == -1)
puri[puri_num++] = {i,j};위쪽 공기청정기는 반시계 방향으로 작동하고, 아래쪽 공기청정기는 시계 방향으로 작동합니다.
2. 현재 미세먼지 위치를 큐로 관리
queue<pair<int, int>> q;큐에는 현재 미세먼지가 존재하는 좌표만 저장합니다.
처음 입력받을 때 미세먼지의 양이 0보다 큰 칸을 큐에 추가합니다.
if (input_data[i][j] > 0)
q.push({i,j});flooding() 함수에서 큐를 모두 비우며 현재 존재하는 미세먼지를 확산시킵니다.
확산과 공기청정기 작동이 끝난 뒤에는 add_queue()를 호출해 다음 초에 확산시킬 미세먼지 좌표를 다시 저장합니다.
3. 미세먼지 확산량 계산
현재 칸의 미세먼지가 인접한 칸으로 확산되는 양은 다음과 같습니다.
int each = input_data[y][x] / 5;정수 나눗셈을 사용하므로 소수점 이하는 자동으로 버려집니다.
각 방향으로 확산할 때마다 현재 칸에서는 each만큼 감소합니다.
input_data[y][x] -= each;그리고 인접한 칸에 추가될 양은 plus_data에 저장합니다.
plus_data[ny][nx] += each;4. 확산할 수 없는 위치 처리
인접한 좌표가 격자를 벗어나면 확산할 수 없습니다.
if (ny < 0 || ny >= R || nx < 0 || nx >= C)
continue;또한 공기청정기가 있는 칸으로도 미세먼지가 확산될 수 없습니다.
if ((puri[0].first == ny && puri[0].second == nx) ||
(puri[1].first == ny && puri[1].second == nx))
continue;실제로 확산 가능한 방향에 대해서만 현재 미세먼지를 감소시키고, 인접한 칸에 확산량을 추가합니다.
5. 확산되는 미세먼지를 별도 배열에 저장하는 이유
미세먼지는 모든 칸에서 동시에 확산됩니다.
하지만 한 칸의 확산량을 다른 칸에 바로 더해버리면, 아직 확산하지 않은 칸이 증가한 미세먼지까지 포함하여 확산할 수 있습니다.
예를 들어 현재 미세먼지의 양이 10인 칸에 다른 칸에서 5가 확산되어 바로 15가 되면, 원래 상태인 10이 아니라 15를 기준으로 확산량을 계산하게 됩니다.
이를 방지하기 위해 증가하는 미세먼지는 별도의 배열에 저장합니다.
int plus_data[50][50];flooding()에서는 원래 칸에서 빠져나가는 양만 input_data에서 감소시키고, 다른 칸으로 들어오는 양은 plus_data에 누적합니다.
이렇게 하면 모든 확산이 같은 시점의 미세먼지 양을 기준으로 처리됩니다.
6. 확산량 반영
모든 미세먼지의 확산이 끝나면 plus_data에 저장한 값을 원본 배열에 더합니다.
void plus_flooding() {
for (int i=0; i<R; i++) {
for (int j=0; j<C; j++) {
if (i == puri[0].first && j == puri[0].second) continue;
if (i == puri[1].first && j == puri[1].second) continue;
input_data[i][j] += plus_data[i][j];
}
}
}공기청정기가 있는 칸은 제외하고 확산된 미세먼지를 반영합니다.
매초 확산을 시작하기 전에는 이전 초의 값이 남아 있지 않도록 plus_data를 초기화합니다.
memset(plus_data, 0, sizeof(plus_data));7. 아래쪽 공기청정기의 시계 방향 순환
아래쪽 공기청정기는 시계 방향으로 공기를 순환시킵니다.
코드에서는 네 구간으로 나누어 미세먼지를 이동시켰습니다.
왼쪽 벽
for (int r = y + 1; r < R - 1; r++) {
input_data[r][0] = input_data[r + 1][0];
}왼쪽 벽의 미세먼지는 아래쪽 값을 받아 위로 이동합니다.
아래쪽 행
for (int c = 0; c < C - 1; c++) {
input_data[R - 1][c] = input_data[R - 1][c + 1];
}아래쪽 행의 미세먼지는 오른쪽 값을 받아 왼쪽으로 이동합니다.
오른쪽 벽
for (int r = R - 1; r > y; r--) {
input_data[r][C - 1] = input_data[r - 1][C - 1];
}오른쪽 벽의 미세먼지는 위쪽 값을 받아 아래로 이동합니다.
공기청정기 행
for (int c = C - 1; c > 1; c--) {
input_data[y][c] = input_data[y][c - 1];
}공기청정기가 있는 행에서는 왼쪽 값을 받아 오른쪽으로 이동합니다.
공기청정기 바로 오른쪽 칸에는 미세먼지가 없는 깨끗한 공기가 들어옵니다.
input_data[y][1] = 0;8. 위쪽 공기청정기의 반시계 방향 순환
위쪽 공기청정기는 반시계 방향으로 공기를 순환시킵니다.
이 경우도 네 구간으로 나누어 처리합니다.
왼쪽 벽
for (int r = y - 1; r >= 1; r--) {
input_data[r][0] = input_data[r - 1][0];
}왼쪽 벽의 미세먼지는 위쪽 값을 받아 아래로 이동합니다.
위쪽 행
for (int c = 0; c < C - 1; c++) {
input_data[0][c] = input_data[0][c + 1];
}위쪽 행의 미세먼지는 오른쪽 값을 받아 왼쪽으로 이동합니다.
오른쪽 벽
for (int r = 0; r < y; r++) {
input_data[r][C - 1] = input_data[r + 1][C - 1];
}오른쪽 벽의 미세먼지는 아래쪽 값을 받아 위로 이동합니다.
공기청정기 행
for (int c = C - 1; c > 1; c--) {
input_data[y][c] = input_data[y][c - 1];
}공기청정기가 있는 행에서는 미세먼지가 오른쪽으로 이동합니다.
마찬가지로 공기청정기 바로 오른쪽에는 깨끗한 공기가 들어옵니다.
input_data[y][1] = 0;9. 값 이동 순서가 중요한 이유
공기청정기의 순환을 구현할 때는 값을 덮어쓰지 않도록 반복문의 진행 방향을 정확히 정해야 합니다.
예를 들어 한 행의 값을 오른쪽으로 이동시키려면 오른쪽 끝에서부터 왼쪽 방향으로 값을 복사해야 합니다.
for (int c = C - 1; c > 1; c--) {
input_data[y][c] = input_data[y][c - 1];
}반대로 왼쪽으로 이동시킬 때는 왼쪽부터 오른쪽 방향으로 순회해야 합니다.
for (int c = 0; c < C - 1; c++) {
input_data[R - 1][c] = input_data[R - 1][c + 1];
}이 순서를 반대로 작성하면 아직 이동하지 않은 원래 값이 덮어써져 잘못된 결과가 발생할 수 있습니다.
10. 다음 확산을 위한 큐 구성
확산과 공기청정기 작동이 모두 끝난 후, 다음 초에 확산될 미세먼지를 다시 큐에 저장합니다.
void add_queue() {
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
if (input_data[r][c] > 0) {
q.push({r, c});
}
}
}
}미세먼지의 양이 0보다 큰 칸만 큐에 넣습니다.
flooding()에서 큐를 모두 비우기 때문에 매초 현재 상태에 해당하는 좌표만 저장됩니다.
11. 남은 미세먼지 계산
T초 동안 시뮬레이션한 뒤 모든 칸의 미세먼지를 더합니다.
int ret = 0;
for (int i=0; i<R; i++) {
for (int j=0; j<C; j++) {
if (i == puri[0].first && j == puri[0].second) continue;
if (i == puri[1].first && j == puri[1].second) continue;
ret += input_data[i][j];
}
}공기청정기가 있는 두 칸은 미세먼지가 아니므로 합에서 제외합니다.
12. 시간복잡도
매초 다음 작업을 수행합니다.
- 미세먼지 확산: 최대
R × C - 확산량 반영:
R × C - 공기청정기 작동:
O(R + C) - 다음 미세먼지 큐 구성:
R × C
따라서 전체 시간복잡도는
O(T × R × C)입니다.
R과 C는 최대 50이고 T는 최대 1,000이므로 충분히 해결할 수 있습니다.
