[백준(BOJ)] 미세먼지 안녕!(17144) C++
문제 : BOJ_17144번 미세먼지 안녕!
문제 설명
완전탐색, bfs
크기가 R*C인 격자판에서 미세먼지가 4방향으로 확장된 뒤, 확장된 이후에 공기청정기에 의해 위쪽은 반시계, 아래쪽은 시계방향으로 미세먼지들이 돌아갑니다.
이 때 공기청정기에 들어간 미세먼지는 사라집니다.
Solution
R과 C의 최댓값이 50, T의 최댓값이 1000이기 때문에, 50501,000=2,500,000임으로 완전탐색이 가능합니다.
미세먼지의 위치와 값을 queue에 다 넣어주고 4방향에 퍼트리는 bfs를 한 뒤, 단순 for문으로 반시계와 시계방향으로 돌리는 방법으로 풀었습니다.
Description
- queue에 해당 위치의 값, 행, 열의 데이터를 넣기위해 pair를 이중으로 사용했습니다.
- 공기청정기의 값은 -1이므로, 마지막 sum에 2를 더해줍니다.
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int R, C, T;
int map[51][51];
int st, ed;
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int main(void) {
scanf("%d%d%d", &R, &C, &T);
for (int i = 1; i <= R; i++) {
for (int j = 1; j <= C; j++) {
scanf("%d", &map[i][j]);
if (map[i][j] == -1) {
if (st == 0) st = i;
else ed = i;
}
}
}
while (T--) {
queue<pair<int, pair<int, int>>> q; // q.push({값,{행,열}});
for (int i = 1; i <= R; i++) {
for (int j = 1; j <= C; j++) {
if (map[i][j] > 0) q.push({ map[i][j],{ i,j } });
}
}
while (!q.empty()) {
int x = q.front().second.first;
int y = q.front().second.second;
int now_val = q.front().first;
q.pop();
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (map[nx][ny] == -1) continue;
if (nx > R || ny > C || nx < 1 || ny < 1) continue;
map[nx][ny] += now_val / 5;
map[x][y] -= now_val / 5;
}
}
// 반시계, 시계방향으로 돌리기 위한 단순 포문
for (int i = st - 1; i >= 2; i--) map[i][1] = map[i - 1][1];
for (int i = 1; i < C; i++) map[1][i] = map[1][i + 1];
for (int i = 1; i < st; i++) map[i][C] = map[i + 1][C];
for (int i = C; i > 2; i--) map[st][i] = map[st][i - 1];
map[st][2] = 0;
for (int i = ed + 1; i < R; i++) map[i][1] = map[i + 1][1];
for (int i = 1; i < C; i++) map[R][i] = map[R][i + 1];
for (int i = R; i > ed; i--) map[i][C] = map[i - 1][C];
for (int i = C; i > 2; i--) map[ed][i] = map[ed][i - 1];
map[ed][2] = 0;
}
int sum = 0;
for (int i = 1; i <= R; i++) {
for (int j = 1; j <= C; j++) {
sum += map[i][j];
}
}
printf("%d\n", sum + 2);
// 공기청정기의 값은 -1이므로, 마지막에 2를 더해준다.
}
PREVIOUS[Node.js] 인터넷 기본 동작