문제 정보
백준 ( BOJ ) 17144 미세먼지 안녕!
문제 풀이 : 시뮬레이션
문제 출처 : https://www.acmicpc.net/problem/17144
( 삼성 역량 테스트 코딩 테스트 문제 )
시작 Thinking
분산을 어떻게 구현 할 것인가 ? -> 테이블을 하나 더 만들자,
실시간으로 테이블에 더해 나가면 앞의 동작이, 뒤의 동작에 영향을 미친다.
굴리는것은 어떻게 굴릴 것인가? -> 직접 구현 하자. 일일이 다 해야 한다.
솔직히.. 이 문제는 진짜 문제에 주어진 대로,
얼마나 빠르고 정확하게 구현 할 수 있니? 묻는 문제 입니다.
당황하지 말고, 천천히 해 보세요.
저같은경우는,
funUp, funDown, funLeft, funDown
이렇게 나누어서 함수로, 구현을 하였지만,
함수로 나누어서 구현 안해도 됩니다.
그냥 그대로 라인타서 구동해도, 8줄 밖에 더 안늘어나요.
( 구현은, 화살표 끝방향에서, 시작점 까지 한칸씩 복사 해 나가면 됩니다. )
그리고 항상 중요한것!.
함수로 짜기!!
함수로 짜야 디버깅 하는데 편합니다.
특.히.나. 이렇게 시뮬레이션 문제에서는,
디버깅 하기 쉽게, 코드를 짜야 문제 풀이가 빠릅니다.
메인에 모두 다 떄려 박아버리면, 디버깅 하기 힘들고,
코드 고치기도 힘듭니다.
저의 메인에서의 함수입니다.
while (t) {
t--;
funAdd();
//cout << "먼지 분산 시작" << endl;
//printAll();
//cout << "먼지 분산 끝 공기청정기 작동 시작" << endl;
funDelete();
//printAll();
}
각 부분에 모두 출력하는 함수를 넣어 놓고, 경과를 비교 해 보면서 가시면 됩니다.
문제가 생긴다면, funAdd() 와, funDelete() 둘중 하나만 주석 처리 하고
디버깅 하는게 더 빠릅니다.
코드
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int r, c, t;
int vaccume = -1;
vector<vector<int>> maps;
vector<vector<queue<int>>> adder;
void printAll() {
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
cout << maps[i][j] << " ";
}
cout << endl;
}
cout << endl;
}
void funAddCheck(int y, int x, int amount) {
int vy[] = { 0,0,1,-1 };
int vx[] = { 1,-1,0,0 };
int ty, tx;
amount /= 5;
for (int i = 0; i < 4; i++) {
ty = vy[i] + y;
tx = vx[i] + x;
if (ty < 0 || tx < 0 || ty >= r || tx >= c)
continue;
if (maps[ty][tx] == -1)
continue;
maps[y][x] -= amount;
adder[ty][tx].push(amount);
}
}
void funAdd() {
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (maps[i][j] > 0)
funAddCheck(i, j, maps[i][j]);
}
}
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
while (!adder[i][j].empty()) {
maps[i][j] += adder[i][j].front();
adder[i][j].pop();
}
}
}
}
void funUp(int y, int x, int end) {
for (int i = y ; i < end; i++) {
maps[i][x] = maps[i + 1][x];
}
}
void funRight(int y, int x, int end) {
for (int i = x; i > end ; i--) {
maps[y][i] = maps[y][i - 1];
}
}
void funDown(int y, int x, int end) {
for (int i = y - 1; i > end; i--) {
maps[i][x] = maps[i - 1][x];
}
}
void funLeft(int y, int x, int end) {
for (int i = x; i < end-1; i++) {
maps[y][i] = maps[y][i + 1];
}
}
void funDelete() {
maps[vaccume - 1][0] = 0;
maps[vaccume + 2][0] = 0;
// 위사이클
funDown(vaccume , 0, 0);
funLeft(0, 0, c);
funUp(0, c-1, vaccume);
funRight(vaccume, c-1, 1);
maps[vaccume ][1] = 0;
// 아래 싸이클
funUp(vaccume + 2, 0, r - 1);
funLeft(r - 1, 0, c );
funDown(r , c - 1, vaccume + 1);
funRight(vaccume + 1, c - 1, 1);
maps[vaccume +1][1] = 0;
}
int main() {
cin >> r >> c >> t;
maps.assign(r, vector<int>(c, 0));
adder.assign(r, vector<queue<int>>(c));
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
cin >> maps[i][j];
if (maps[i][j] == -1 && vaccume == -1)
vaccume = i;
}
}
//printAll();
while (t) {
t--;
funAdd();
//cout << "먼지 분산 시작" << endl;
//printAll();
//cout << "먼지 분산 끝 공기청정기 작동 시작" << endl;
funDelete();
//printAll();
}
int result = 0;
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (maps[i][j] != -1)
result += maps[i][j];
}
}
cout << result;
return 0;
}
/*
6 6 1
0 0 0 0 0 0
0 15 0 0 15 0
-1 0 0 0 0 0
-1 0 0 0 0 0 0
0 15 0 0 15 0
0 0 0 0 0 0
6 6 1
1 2 3 4 5 6
6 5 4 3 2 1
-1 2 3 4 5 6
-1 6 5 4 3 2
1 2 3 4 5 6
6 5 4 3 2 1
1 2 3 4 5 6
*/
후기
소요 시간 : 56 분.
너무 오래 걸린.. 디버깅이 너무 오래 걸린…