[G4] 백준 17144번 미세먼지 안녕! C++ 구현, 시뮬레이션

리뷰

 

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

간만에 풀어보는 100줄 이상 되는 구현 문제

 

 

전역 변수

• r, c, t : 행의 크기 r, 열의 크기 c, 공기 청정기를 작동할 횟수 t
• lst : 맵의 상태를 저장하기 위한 2차 정수 배열
• dx, dy : 공기 청정기 및 미세 먼지 확산 시뮬레이션을 위한 방향 배열
• Air : 공기 청정기의 위치를 표시하기 위한 구조체
• cleaner : 공기 청정기 위치를 저장하기 위한 Air타입 배열
• Dust : 맵에 존재하는 미세먼지 정보를 표시하기 위한 구조체

 

함수

1. input

void input()

 

변수 및 맵 정보와 공기 청정기 정보를 입력받고 저장하기 위한 함수

1. r, c, t를 입력 받고 공기 청정기의 인덱스로 사용할 정수형 변수 idx를 0으로 초기화 한다.
2. r * c크기의 맵 정보를 입력 받는다.
3. 이때 값이 -1인 정보는 cleaner배열의 idx 인덱스를 후위증가하여 위치를 기록해 준다.

 

2. spread

void spread(queue<Dust>& q)

 

미세먼지의 확산을 시뮬레이션 하기 위한 함수

1. 매개변수로 미세 먼지의 위치와 양이 저장된 Dust타입의 큐를 참조한다.
2. q가 빌때까지 미세먼지를 하나씩 꺼낸다.
3. cnt변수를 0으로 초기화 하고, 4방향을 탐색하고 확산할 수 있다면 cnt를 증가시킨다.
4. 다시 4방향을 탐색하여 cnt의 개수에 맞추어 확산을 시뮬레이션 해준다.
5. 이때 맵을 직접 참조하지 않고, 구조체 내의 미세먼지 개수를 참조해 주어야 한다.

 

3. print

void print()

 

디버깅을 위한 함수, 각 시뮬레이션 단계에서의 미세먼지의 확산 및 바람의 이동을 확인한다.

 

4. blow

void blow()

 

공기청정기에서 나온 바람의 이동을 시뮬레이션 하기 위한 함수

1. 공기청정기의 상부 부터 바람을 내뿜어 맵의 범위 내에서 상우하좌로 이동한다.
2. 이동하면서 현재 위치와 다음 위치의 미세먼지의 위치를 swap메서드를 통해 변경해준다.
3. 바람의 이동이 완료되었다면 바람이 나오는 가장 첫번째 위치를 0으로 변경해 준다.
4. 공기청정기 하부 또한 동일한 방식으로 시뮬레이션 하되 방향의 방향은 하부에 맞게 진행한다.
5. 방향 배열에서 상부는 0~3번 인덱스, 하부는 4~7번 인덱스를 사용해 주면 된다.

 

5. solution

void solution()

 

각 테스트 케이스에서 미세먼지의 확산과 바람을 돌리는 시뮬레이션을 진행할 함수

1. t번의 반복문으로 공기청정기 작동을 시뮬레이션 해준다.
2. Dust타입의 큐 q를 초기화 해주고, 맵을 돌며 1이상인 값이 있다면 큐에 넣어준다.
3. spread함수에 q를 매개변수로 전달하여 미세먼지 확산을 시뮬레이션 해준다.
4. blow함수를 통해 공기 청정기의 바람 이동을 시뮬레이션 해준다.

 

6. chk

int chk()

 

현재 맵에 남아있는 미세 먼지의 개수를 세어주기 위한 함수

1. 변수 ans를 0으로 초기화 해준다.
2. 맵을 탐색하며 1이상인 값을 만난 경우 ans에 해당 값만큼 더해준다.
3. ans에 저장된 값을 리턴해 준다.

 

문제풀이

1. input 함수를 통해 변수 및 배열에 값을 입력 받아 초기화를 진해앻 준다.
2. solution 함수를 통해 t번의 공기청정기 작동을 시뮬레이션 해준다.
3. chk 함수를 통해 result변수에 맵에 남아있는 미세먼지의 개수를 저장해 준다.
4. result에 저장된 값을 출력해 준다.

 

참고 사항

구현 했던 내용에 이슈가 있다면 print함수 등을 통해 디버깅을 진행하며 문제를 푸는 것을 추천한다.

 

 

정답 코드

#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;

int r, c, t;
int lst[51][51];
int dx[] = { -1, 0, 1, 0, 1, 0, -1, 0 };
int dy[] = { 0, 1, 0, -1, 0, 1, 0, -1 };

struct Air {
	int x, y;
};

Air cleaner[2];

struct Dust {
	int x, y, c;
};

void input() {
	cin >> r >> c >> t;
	int idx = 0;
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			cin >> lst[i][j];
			if (lst[i][j] == -1) cleaner[idx++] = { i, j };
		}
	}
}

void spread(queue<Dust>& q) {
	while (!q.empty()) {
		Dust dust = q.front(); q.pop();
		int cx = dust.x, cy = dust.y, cc = dust.c;

		int cnt = 0;
		for (int i = 0; i < 4; i++) {
			int nx = cx + dx[i], ny = cy + dy[i];
			if (0 <= nx && nx < r && 0 <= ny && ny < c && lst[nx][ny] != -1) cnt++;
		}

		for (int i = 0; i < 4; i++) {
			int nx = cx + dx[i], ny = cy + dy[i];
			if (0 <= nx && nx < r && 0 <= ny && ny < c && lst[nx][ny] != -1) lst[nx][ny] += cc / 5;
		}
		lst[cx][cy] -= cc / 5 * cnt;
	}
}

void print() {
	cout << "\n";
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			cout << lst[i][j] << " ";
		}
		cout << "\n";
	}
}

void blow() {
	int sx = cleaner[0].x, sy = cleaner[0].y;
	for (int i = 0; i < 4; i++) {
		int nx = sx + dx[i], ny = sy + dy[i];
		while (0 <= nx && nx <= cleaner[0].x && 0 <= ny && ny < c) {
			swap(lst[nx][ny], lst[sx][sy]);
			sx = nx, sy = ny;
			nx += dx[i], ny += dy[i];
			//print();
		}
	}
	lst[sx][sy + 1] = 0;

	sx = cleaner[1].x, sy = cleaner[1].y;
	for (int i = 4; i < 8; i++) {
		int nx = sx + dx[i], ny = sy + dy[i];
		while (cleaner[1].x <= nx && nx < r && 0 <= ny && ny < c) {
			swap(lst[nx][ny], lst[sx][sy]);
			sx = nx, sy = ny;
			nx += dx[i], ny += dy[i];
			//print();
		}
	}
	lst[sx][sy + 1] = 0;
}

void solution() {
	while (t--) {
		queue<Dust> q;
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++) {
				if (lst[i][j] > 0) q.push({ i, j ,lst[i][j] });
			}
		}
		spread(q);
		blow();
	}
}

int chk() {
	int ans = 0;
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			if (lst[i][j] > 0) ans += lst[i][j];
		}
	}
	return ans;
}

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

	input();
	solution();
	int result = chk();
	cout << result;
}