• Home
  • About
    • 코드좀비 photo

      코드좀비

      An amazing website.

    • Learn More
    • Github
  • Posts
    • All Posts
    • All Tags
  • Projects

[BOJ] 백준 17144 미세먼지 안녕! 간단한설명과 코드 C++

28 Mar 2020

Reading time ~4 minutes

문제 정보

백준 ( 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 분.

너무 오래 걸린.. 디버깅이 너무 오래 걸린…



백준C++시뮬레이션 Share Tweet +1