[BOJ] 17144. 미세먼지 안녕!

[문제]

https://www.acmicpc.net/problem/17144

17144번: 미세먼지 안녕!

[풀이]

 

1) 맵의 형태 보존이 중요한 문제이다. 

 

2) 1열의 어느 2 행에는 공기청정기가 설치되어있고 다른 칸들은 모두 미세먼지가 있거나, 미세먼지가 있을 수 있는 공간이다. 

 

3) 1초에 두 가지 프로세스가 진행된다. (총 T초간 진행)

 

• 미세먼지 확산 (상하좌우로 퍼진다. 단, 벽과 공기청정기가 있는 칸은 퍼지지 않는다.) 

  퍼지는 미세먼지의 양은 현재 미세먼지의 1/5

• 공기청정기 작동 (공기청정기가 위치한 행 중 위쪽은 반시계방향으로 흐르고, 아래쪽은 시계방향으로 흐른다. 공기청정기로 들어온 미세먼지는 제거된다.

4) 미세먼지 확산 (SpreadDust()) 

 

현재 칸에 있는 미세먼지의 양에서 5를 나눈 만큼 인접한 칸들에 확산된다. 

현재 칸의 미세먼지 양을 계속 가지고 있어야 하기 때문에 c_map에 확산된 먼지 양을 저장한다. 

 

현재 칸이 0보다 큰 값을 가지고 있다면 c_map에 미세먼지를 확산시키고, 0보다 작다면 공기청정기이기 때문에 c_map에 -1을 넣어준다. 

 

map에 c_map을 복사한다. 

 

5)  공기청정기를 작동시킬 때 또 다른 맵(c_map2)에 이동한 미세먼지들을 저장한다. 

반시계방향 

 

• 왼쪽-> 오른쪽

• 아래쪽 -> 위쪽

• 오른쪽-> 왼쪽 

• 위쪽-> 아래쪽 (공기청정기로 들어가게 되는 것과 아닌 것을 구별해야 한다.)

시계방향 

 

• 오른쪽->왼쪽 

• 위쪽-> 아래쪽

• 왼쪽-> 오른쪽

• 아래-> 위쪽 (공기청정기로 들어가게 될 것과 아닌 것을 구별해야한다.)

7) map 에 남아있는 미세먼지의 수를 더하여 정답을 도출한다. 

 

---

#include <iostream> #include <vector> #include <cstring> using namespace std; int r, c, t; int map[51][51]; int pure[2][2]; int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1}; void print() { cout << '\n'; for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { cout << map[i][j] << ' '; } cout << '\n'; } cout << '\n'; } void turn(int dir) { //공기청정기에서 시작해서 현재 칸으로 이전의 값을 불러드린다. if (dir > 0) { //시계방향 int x = pure[1][0]; int y = pure[1][1]; //^ for (int i = x+1; i < r-1; i++) { map[i][y] = map[i+1][y]; } //<- for (int i = 0; i < c-1; i++) { map[r-1][i] = map[r-1][i+1]; } //V for (int i = r-1; i > x; i--) { map[i][c-1] = map[i-1][c-1]; } //-> for (int i = c-1; i > y+1; i--) { map[x][i] = map[x][i-1]; } map[x][y+1] = 0; } else { int x = pure[0][0]; int y = pure[0][1]; //반시계방향 //V for (int i = x-1; i > 0; i--) { map[i][y] = map[i-1][y]; } //<- for (int i = 0; i < c-1; i++) { map[0][i] = map[0][i+1]; } //^ for (int i = 0; i < x; i++) { map[i][c-1] = map[i+1][c-1]; } //-> for (int i = c-1; i > y+1; i--) { map[x][i] = map[x][i-1]; } map[x][y+1] = 0; } } void turnOnPureSystem() { turn(1); // print(); turn(-1); // print(); } void spreadDust() { int c_map[51][51]; memset(c_map, 0, sizeof(map)); //확산된 미세먼지를 저장 for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { if (map[i][j] == -1) c_map[i][j] = -1; else if (map[i][j]) { //확산 int cnt = 0; for (int d = 0; d < 4; d++) { int nx = i + dx[d]; int ny = j + dy[d]; if (nx < 0 || nx >= r || ny < 0 || ny >= c || map[nx][ny] == -1) { continue; } c_map[nx][ny] += map[i][j] / 5; cnt++; } c_map[i][j] += map[i][j] - (map[i][j] / 5) * cnt; } } } memcpy(map, c_map, sizeof(map)); // print(); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> r >> c >> t; bool flag = false; for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { cin >> map[i][j]; if (map[i][j]==-1) { if (!flag) { pure[0][0] = i; pure[0][1] = j; flag = true; } else { pure[1][0] = i; pure[1][1] = j; } } } } while (t--) { //미세먼지 확산 spreadDust(); turnOnPureSystem(); } int sum = 0; for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { if (map[i][j] > 0) { sum += map[i][j]; } } } cout << sum << '\n'; return 0; }