[삼성코테기출문제] 미세먼지 안녕!

미세먼지 안녕!

문제

풀었다.. 풀었다!! 상반기 sw역량테스트 기출문제다. 미세먼지 안녕! , 낚시왕 둘 다 풀지 못하고 한숨만 푹푹 쉬면서 풀 수 있을거같았는데 하며 술을 퍼마셨던 그 날…
잊을 수 없는 문제다… 이번에 재도전하면서 1시간 반정도 걸려서 문제를 풀어냈다. 공기청정기가 도는 방향을 처리를 제대로 못해줬었는데 그 부분을 해결했다.

문제 풀이

입출력 조건

먼저 먼지가 확산되는 과정을 구하는 것은 쉽게 구현했다. 워낙 bfs연습을 많이해서 익숙해진것같다. 다만 주의할 점은 모든 먼지가 동시에 확산된다는 점! 한 칸을 변경시켜 다른 칸이 영향을 받은 상태로 다음 칸을 처리를 하면 안된다는 것이다.

풀이 과정

1. 입력 조건을 입력 받으면서 공기청정기의 위치를 따로 저장해 둔다.
2. 큐를 초기화하고, 맵에 먼지가 있으면 해당 좌표와 먼지의 양을 큐에 넣는다.
3. 먼지 확산 과정으로 넘어간다. 현재 좌표의 정보를 pop하여 꺼내고 현재좌표의 먼지양/5을 인접 칸에 더해주고 현재 칸에 빼준다.
4. 먼지 확산 과정을 끝내고 공기청정기를 과정으로 넘어간다. dfs를 이용하여 현재 칸에 다음 칸의 먼지를 채워주며 dfs를 도는데 이 때 중요한 것은

    if (n == 0 && (ny < 0 || nx < 0 || ny > Clear[n].y || nx > C-1)) {
        dIdx += 1;
        ny = y + dy[d[n][dIdx]];
        nx = x + dx[d[n][dIdx]];
    }
    if (n == 1 && (ny < Clear[n].y || nx < 0 || ny > R-1 || nx > C-1)) {
        dIdx += 1;
        ny = y + dy[d[n][dIdx]];
        nx = x + dx[d[n][dIdx]];
    }
   

   n은 위쪽 아래쪽 공기청정기를 의미하고 위쪽은 반시계방향 아래쪽은 시계방향으로 돌아야하므로 그 처리를 위와 같이 해준다.

5. 이 과정을 T번 반복하여 그 후 남아있는 먼지의 양을 세어 출력해준다.

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
const int MAX = 50;
int R, C, T, ans;
int Map[MAX][MAX];
int Visit[MAX][MAX];
int dx[4] = { 0,1,0,-1 };
int dy[4] = { -1,0,1,0 };
int d[2][4] = { { 0,1,2,3 }, { 2,1,0,3 } };
typedef struct Pos {
	int x, y;
	int dust;
};
vector<Pos> Clear;
queue<Pos> Q;

void Input() {
	cin >> R >> C >> T;
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			cin >> Map[i][j];
			if (Map[i][j] == -1) Clear.push_back({ j, i });
		}
	}
}
//dir 0북, 1동, 2남, 3서
//dir 2남, 1동, 0북, 3서
void ActClear(int n, int x, int y, int dIdx) {
	if (Clear[n].x == x && Clear[n].y == y) {
		Map[y][x + 1] = 0;
		return;
	}
	Visit[y][x] = true;
	int nx, ny;
	ny = y + dy[d[n][dIdx]];
	nx = x + dx[d[n][dIdx]];
	if (n == 0 && (ny < 0 || nx < 0 || ny > Clear[n].y || nx > C-1)) {
		dIdx += 1;
		ny = y + dy[d[n][dIdx]];
		nx = x + dx[d[n][dIdx]];
	}
	if (n == 1 && (ny < Clear[n].y || nx < 0 || ny > R-1 || nx > C-1)) {
		dIdx += 1;
		ny = y + dy[d[n][dIdx]];
		nx = x + dx[d[n][dIdx]];
	}
	Map[y][x] = Map[ny][nx];
	ActClear(n, nx, ny, dIdx);

}
void Spread() {
	while (!Q.empty()) {
		int curx = Q.front().x;
		int cury = Q.front().y;
		int curdust = Q.front().dust;
		Q.pop();
		int sp = curdust / 5;
		for (int i = 0; i < 4; i++) {
			int nx = curx + dx[i];
			int ny = cury + dy[i];
			if (nx >= 0 && nx < C&&ny >= 0 && ny < R) {
				if (Map[ny][nx] > -1) {
					Map[ny][nx] += sp;
					Map[cury][curx] -= sp;
				}
			}
		}
	}
}
void Process() {
	for (int i = 0; i < T; i++) {
		while (!Q.empty())Q.pop();
		for (int a = 0; a < R; a++) {
			for (int b = 0; b < C; b++) {
				if (Map[a][b] > 0)Q.push({ b,a ,Map[a][b] });
			}
		}
		Spread();
		ActClear(1, Clear[1].x, Clear[1].y + 1, 0);
		ActClear(0, Clear[0].x, Clear[0].y - 1, 0);
	}
	for (int i = 0; i < R; i++)
		for (int j = 0; j < C; j++)
			if (Map[i][j] > 0)
				ans += Map[i][j];
	cout << ans << "\n";

}
void Solution() {
	Input();
	Process();
}
int main() {
	freopen("22.in", "r", stdin);
	Solution();
	return 0;
}