[BoJ-17144] 미세먼지 안녕! 문제 풀이

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

17144번: 미세먼지 안녕!

 

2019년 상반기 삼성전자 ds 기출문제중 한 문제와 유사한 문제입니다.

 

저는 BFS를 이용해 풀었고 난이도는 이전의 삼성 역량테스트와 비교했을때 어렵지 않은 수준이었습니다.

 

그냥 문제에 나오는대로 구현만 해주면 되는 문제...

 

하지만 전 멍청한 관계로 코드를 길게 작성했습니다;;

 

---------------------------------------------------------------------------------------------------------------------------------

 

미세먼지 확산 -> bfs를 이용해 확산

공기청정기에 의한 미세먼지 이동 -> while문으로 한 방향씩 이동시켰습니다. (동, 서, 남, 북 따로 구현)

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <queue>

using namespace std;

struct POSITION {
	int y, x;
};

int r, c, t;
int res;
int map[50][50];
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,-1,1 };
queue<POSITION> q;

int isDirection(int u, int v) {
	int direction = 0;

	for (int dir = 0; dir < 4; dir++) {
	
		int ny = u + dy[dir];
		int nx = v + dx[dir];

		if (map[ny][nx] == -1) continue;
		if (ny < 0 || ny >= r || nx < 0 || nx >= c) continue;

		direction += 1;
	}
	return direction;
}

int main(void) {

	scanf("%d %d %d", &r, &c, &t);

	POSITION cleaner_top, cleaner_bot;
	bool clean_flag = false;

	for (int y = 0; y < r; y++) {
		for (int x = 0; x < c; x++) {
			scanf("%d", &map[y][x]);
			if (map[y][x] > 0) {
				q.push({ y,x });
			}

			if (map[y][x] == -1) {
				if (!clean_flag) {
					cleaner_top.y = y, cleaner_top.x = x;
					clean_flag = true;
				}
				else {
					cleaner_bot.y = y, cleaner_bot.x = x;
				}
			}
		}
	}

	while (t--) {
		int bin[50][50] = { 0 };

		//미세먼지 확산
		while (!q.empty()) {
			POSITION cur;
			cur = q.front();
			q.pop();

			int direc = isDirection(cur.y, cur.x);

			for (int dir = 0; dir < 4; dir++) {
				POSITION next;
				next.y = cur.y + dy[dir];
				next.x = cur.x + dx[dir];

				if (map[next.y][next.x] == -1) continue;
				if (next.y < 0 || next.y >= r || next.x < 0 || next.x >= c) continue;

				bin[next.y][next.x] += map[cur.y][cur.x] / 5;
			}
				map[cur.y][cur.x] = map[cur.y][cur.x] - (map[cur.y][cur.x] / 5) * direc;
		}

		for (int y = 0; y < r; y++) {
			for (int x = 0; x < c; x++) {
				map[y][x] += bin[y][x];
			}
		}

		//공기청정기 작동
		//위
		POSITION cur_top;
		cur_top = cleaner_top;
		while (cur_top.y > 0) {
			if (map[cur_top.y][cur_top.x] == -1) map[cur_top.y - 1][cur_top.x] = 0;
			else if(map[cur_top.y - 1][cur_top.x] > 0){
				map[cur_top.y][cur_top.x] = map[cur_top.y - 1][cur_top.x];
				map[cur_top.y - 1][cur_top.x] = 0;
			}
			cur_top.y -= 1;
		}
		while (cur_top.x < c - 1) {
			map[cur_top.y][cur_top.x] = map[cur_top.y][cur_top.x + 1];
			map[cur_top.y][cur_top.x + 1] = 0;
			cur_top.x += 1;
		}

		while (cur_top.y < cleaner_top.y) {
			map[cur_top.y][cur_top.x] = map[cur_top.y + 1][cur_top.x];
			map[cur_top.y + 1][cur_top.x] = 0;
			cur_top.y += 1;
		}

		while (cur_top.x > 0) {
			if (map[cur_top.y][cur_top.x - 1] == -1) map[cur_top.y][cur_top.x] = 0;
			else if (map[cur_top.y][cur_top.x - 1] > 0) {
				map[cur_top.y][cur_top.x] = map[cur_top.y][cur_top.x - 1];
				map[cur_top.y][cur_top.x - 1] = 0;
			}
			cur_top.x -= 1;
		}

		//아래
		POSITION cur_bot;
		cur_bot = cleaner_bot;

		while (cur_bot.y < r - 1) {
			if (map[cur_bot.y][cur_bot.x] == -1) map[cur_bot.y + 1][cur_bot.x] = 0;
			else if (map[cur_bot.y + 1][cur_bot.x] > 0) {
				map[cur_bot.y][cur_bot.x] = map[cur_bot.y + 1][cur_bot.x];
				map[cur_bot.y + 1][cur_bot.x] = 0;
			}
			cur_bot.y += 1;
		}

		while (cur_bot.x < c - 1) {
			map[cur_bot.y][cur_bot.x] = map[cur_bot.y][cur_bot.x + 1];
			map[cur_bot.y][cur_bot.x + 1] = 0;
			cur_bot.x += 1;
		}

		while (cur_bot.y > cleaner_bot.y) {
			map[cur_bot.y][cur_bot.x] = map[cur_bot.y - 1][cur_bot.x];
			map[cur_bot.y - 1][cur_bot.x] = 0;
			cur_bot.y -= 1;
		}

		while (cur_bot.x > 0) {
			if (map[cur_bot.y][cur_bot.x - 1] == -1)  map[cur_bot.y][cur_bot.x] = 0;
			else {
				map[cur_bot.y][cur_bot.x] = map[cur_bot.y][cur_bot.x - 1];
				map[cur_bot.y][cur_bot.x - 1] = 0;
			}
			cur_bot.x -= 1;
		}

		for (int y = 0; y < r; y++) {
			for (int x = 0; x < c; x++) {
				if (map[y][x] > 0) q.push({ y,x });
			}
		}

	}

	//결과 합
	for (int y = 0; y < r; y++) {
		for (int x = 0; x < c; x++) {
			if (map[y][x] > 0) res += map[y][x];
		}
	}
	printf("%d\n", res);

	getchar();
	getchar();

	return 0;
}