백준 17144 미세먼지 안녕! (c++) : 피너클

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

17144번: 미세먼지 안녕!

귀찮은 구현문제다.

int r, c, t;
int map[51][51];
int dy[] = { 1, 0, -1, 0 };
int dx[] = { 0, 1, 0, -1 };
vector<pair<int, int>> v;

r, c, y, map은 입력받을 값들이고 dy, dx는 미세먼지가 확산될때 사용할것이다.

v에는 공기청정기의 위치가 들어갈것이다.

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) v.push_back({ i, j });
	}
}

값들을 입력받는다. 이때 입력받은 값이 -1이면 v에 위치를 집어넣는다.

while (t-- > 0) {
	dust();
	clean();
}

이제 t만큼 미세먼지를 확산 시키고 공기청정기를 돌리면 된다.

dust가 미세먼지 확산이고

clean이 공기청정기 돌리기다.

void dust() {
	int up[51][51];
	memset(up, 0, sizeof(up));

up은 미세먼지가 확산될때 사용할것이다. 0으로 초기화해준다.

모든 미세먼지를 돌아보며 미세먼지가 확산되는 값들을 up에 집어넣은 뒤 마지막에 한꺼번에 더해줄것이다.

for (int i = 0; i < r; i++) {
	for (int j = 0; j < c; j++) {
		if (map[i][j] != 0 && map[i][j] != -1) {
			spread(up, i, j);
		}
	}
}

map을 돌아보며 만약 비어있지 않고 공기청정기가 아니라면 확산 시켜준다.

여기서 확산 시킬때 spread함수를 이용해준다.

void spread(int up[51][51], int y, int x) {
	int sp = map[y][x] / 5;
	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (0 <= ny && ny < r && 0 <= nx && nx < c) {
			if (map[ny][nx] == -1) continue;
			map[y][x] -= sp;
			up[ny][nx] += sp;
		}
	}
}

그냥 현재 위치에서 4방향을 돌아보며 범위에서 안벗어나고 -1이 아니면 

map[y][x] / 5만큼 현재값을 빼고 up[ny][nx]에는 map[y][x] / 5 만큼 더해주면 된다.

	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			map[i][j] += up[i][j];
		}
	}
}

spread함수를 돌린뒤 dust에서 모든 up을 돌아보며 map에 더해준다.

 

이제 clean함수다. 가장 귀찮은 함수다.

void clean() {
	int uy = v[0].first;
	int ux = v[0].second;

uy와 ux는 위에 있는 공기청정기의 위치다. 미세먼지를 옮길때

현재 값을 다음 위치로 넘기는게 아닌 이전 값을 현재 위치로 옮길것이다.

10

19

3

91

2

위의 배열의 모든 값을 왼쪽에서 오른쪽으로 옮긴다고 생각해보자. 진짜로 왼쪽에서 오른쪽으로 옮기면

0

10

3

91

2

0번째 값을 1번째 위치로 옮긴후 1번째 값을 2번째 위치로 옮겨야 하지만 이미 값은 사라졌다.

그렇기에 이전 값을 현재 위치로 옮길것이다.

10

19

3

91

2

위의 배열을 전부 왼쪽에서 오른쪽으로 옮길때 오른쪽부터 시작해

10

19

3

91

91

3번째 값을 4번째로 옮기고

10

19

3

3

91

2번째 값을 3번째로 옮겼다. 이를 반복하면

10

10

19

3

91

이 되고 마지막에 0번째 값만 0으로 바꿔주면 옮기는 것이 끝난다.

	for (int i = uy - 1; i > 0; i--) map[i][ux] = map[i - 1][ux];
	for (int i = ux; i < c - 1; i++) map[0][i] = map[0][i + 1];
	for (int i = 0; i < uy; i++) map[i][c - 1] = map[i + 1][c - 1];
	for (int i = c - 1; i > ux + 1; i--) map[uy][i] = map[uy][i - 1];
	map[uy][ux + 1] = 0;

위의 내용을 코드로 짠것이다.

	int dy = v[1].first;
	int dx = v[1].second;
	for (int i = dy + 1; i < r - 1; i++) map[i][dx] = map[i + 1][dx];
	for (int i = dx; i < c - 1; i++) map[r - 1][i] = map[r - 1][i + 1];
	for (int i = r - 1; i > dy - 1; i--) map[i][c - 1] = map[i - 1][c - 1];
	for (int i = c - 1; i > dx + 1; i--) map[dy][i] = map[dy][i - 1];
	map[dy][dx + 1] = 0;
}

그후 아래 공기청정기도 똑같은 작업을 해준다. 작업은 같지만 반복문이 미묘하게 다른걸 알수있다.

이래서 귀찮은 구현문제라고 한것이다.

int ans = 0;
for(int i = 0; i < r; i++)
	for (int j = 0; j < c; j++) {
		if (map[i][j] != -1) ans += map[i][j];
	}
cout << ans << endl;

메인함수에서 while문이 끝난뒤 ans에 모든 미세먼지를 더하고 출력하면 끝이다.

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;

int r, c, t;
int map[51][51];
int dy[] = { 1, 0, -1, 0 };
int dx[] = { 0, 1, 0, -1 };
vector<pair<int, int>> v;

void spread(int up[51][51], int y, int x) {
	int sp = map[y][x] / 5;
	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (0 <= ny && ny < r && 0 <= nx && nx < c) {
			if (map[ny][nx] == -1) continue;
			map[y][x] -= sp;
			up[ny][nx] += sp;
		}
	}
}

void dust() {
	int up[51][51];
	memset(up, 0, sizeof(up));
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			if (map[i][j] != 0 && map[i][j] != -1) {
				spread(up, i, j);
			}
		}
	}
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			map[i][j] += up[i][j];
		}
	}
}

void clean() {
	int uy = v[0].first;
	int ux = v[0].second;
	for (int i = uy - 1; i > 0; i--) map[i][ux] = map[i - 1][ux];
	for (int i = ux; i < c - 1; i++) map[0][i] = map[0][i + 1];
	for (int i = 0; i < uy; i++) map[i][c - 1] = map[i + 1][c - 1];
	for (int i = c - 1; i > ux + 1; i--) map[uy][i] = map[uy][i - 1];
	map[uy][ux + 1] = 0;

	int dy = v[1].first;
	int dx = v[1].second;
	for (int i = dy + 1; i < r - 1; i++) map[i][dx] = map[i + 1][dx];
	for (int i = dx; i < c - 1; i++) map[r - 1][i] = map[r - 1][i + 1];
	for (int i = r - 1; i > dy - 1; i--) map[i][c - 1] = map[i - 1][c - 1];
	for (int i = c - 1; i > dx + 1; i--) map[dy][i] = map[dy][i - 1];
	map[dy][dx + 1] = 0;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	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) v.push_back({ i, j });
		}
	}
	while (t-- > 0) {
		dust();
		clean();
	}
	int ans = 0;
	for(int i = 0; i < r; i++)
		for (int j = 0; j < c; j++) {
			if (map[i][j] != -1) ans += map[i][j];
		}
	cout << ans << endl;
}

전체코드다.