TIL Blog💻

[BOJ] 미세먼지 안녕!(17144)

  • Jan 29, 2020

[백준(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

  1. queue에 해당 위치의 값, 행, 열의 데이터를 넣기위해 pair를 이중으로 사용했습니다.
  2. 공기청정기의 값은 -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를 더해준다.
}
Search