백준 17144 c++ "미세먼지 안녕!" -PlusUltraCode-

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

 

 

 

 

 

 

 

[필자사고]

구현 문제이다. 구현 문제의 가장 큰 해결법은 함수들을 각각의 역할에 맞게 정리하여 세분화 해야 된다는 점이다.

한번에 모든 기능을 다 넣으려고 하면 디버깅 시간이 말도안되게 오래 걸릴 뿐더러 이해하기 어려울 수 있다.

 

필자는 문제에서 주어진 설명대로 함수들을 나눴고 아래와 같이 코드를 작성하였다.

 

[해설]

 

1. 입력 처리 (Input 함수):
   • R (행 수), C (열 수), T (시간) 값을 입력받습니다.
   • 배열 Arr를 R x C 크기로 초기화하고 각 위치의 미세먼지 양을 입력받습니다.
   • 공기청정기의 위치를 저장합니다.
2. 유틸리티 함수:
   • isInside: 주어진 좌표가 배열의 유효 범위 내에 있는지 확인합니다.
   • CArr_init: 현재 배열 Arr의 상태를 복사하여 CArr 배열을 초기화합니다.
3. 공기청정기 동작 (RotateUp, RotateDown 함수):
   • RotateUp: 상단 공기청정기의 순환 동작을 시뮬레이션합니다.
   • RotateDown: 하단 공기청정기의 순환 동작을 시뮬레이션합니다.
4. 미세먼지 확산 (One_diffusion, All_diffusion 함수):
   • One_diffusion: 특정 위치에서 미세먼지가 주변으로 확산되는 것을 계산합니다.
   • All_diffusion: 배열 전체의 미세먼지가 확산되도록 합니다.
5. 출력 (Print 함수):
   • 최종 배열 상태를 출력합니다.
6. 시뮬레이션 실행 (GameStart 함수):
   • 입력된 시간 T 동안 미세먼지 확산과 공기청정기 동작을 반복합니다.
7. 메인 함수:
   • Input 함수를 호출하여 초기 입력을 받고, GameStart 함수로 시뮬레이션을 시작합니다.
   • 최종 결과를 출력합니다.

아래는 프로그램의 전체 코드입니다.

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int dy[4] = { 0,-1,0,1 };
int dx[4] = { 1,0,-1,0 };

typedef pair<int, int> Node;

vector<vector<Node>> Arr;

int R, C, T;
int Result = 0;
int allDustCount = 2;
Node machineIndex = { -1,-1 };

void Input() {
	cin >> R >> C >> T;

	Arr.resize(R);
	for (int i = 0; i < R; i++) {
		Arr[i].resize(C);
	}
	for (int i = 0; i < R; i++) {
		for (int k = 0; k < C; k++) {
			int num;
			cin >> num;
			Arr[i][k] = { num,0 };
			allDustCount += num;
			if (num == -1) {
				if (machineIndex.first == -1) {
					machineIndex.first = i;
				}
				else {
					machineIndex.second = i;
				}
			}
		}
	}
}

bool isInside(int sero, int garo) {
	return (sero >= 0 && sero < R && garo >= 0 && garo < C);
}

void CArr_init(vector<vector<Node>>& CArr) {
	CArr.clear();
	CArr.resize(R);

	for (int i = 0; i < R; i++) {
		CArr[i].resize(C);
	}
	CArr = Arr;

	for (int i = 0; i < C; i++) {
		CArr[0][i] = { 0,0 };
		CArr[R - 1][i] = { 0,0 };
		CArr[machineIndex.first][i] = { 0,0 };
		CArr[machineIndex.second][i] = { 0,0 };
	}
	for (int i = 0; i < R; i++) {
		CArr[i][0] = { 0,0 };
		CArr[i][C - 1] = { 0,0 };
	}
	CArr[machineIndex.first][0] = { -1,0 };
	CArr[machineIndex.second][0] = { -1,0 };
}

void RotateUp() {
	vector<vector<Node>> CArr;
	CArr_init(CArr);

	int nowMachine = machineIndex.first;

	for (int i = nowMachine-1; i >= 0; i--) {
		CArr[i + 1][0] = Arr[i][0];
	}
	for (int i = 1; i < C; i++) {
		CArr[0][i-1] = Arr[0][i];
	}
	for (int i = 0; i < nowMachine; i++) {
		CArr[i][C - 1] = Arr[i + 1][C - 1];
	}
	for (int i = C - 1; i > 1; i--) {
		CArr[nowMachine][i] = Arr[nowMachine][i - 1];
	}

	Result += CArr[nowMachine][0].first;
	CArr[nowMachine][0] = { -1,0 };
	for (int i = 0; i <= nowMachine; i++) {
		Arr[i] = CArr[i];
	}
}

void RotateDown() {
	vector<vector<Node>> CArr;
	CArr_init(CArr);
	int nowMachine = machineIndex.second;

	for (int i = nowMachine +1; i<R; i++) {
		CArr[i -1][0] = Arr[i][0];
	}
	for (int i = 1; i < C; i++) {
		CArr[R-1][i - 1] = Arr[R-1][i];
	}
	for (int i = R-2; i >=nowMachine; i--) {
		CArr[i+1][C - 1] = Arr[i][C - 1];
	}
	for (int i = C - 1; i > 1; i--) {
		CArr[nowMachine][i] = Arr[nowMachine][i - 1];
	}
	Result += CArr[nowMachine][0].first;
	CArr[nowMachine][0] = { -1,0 };

	for (int i = nowMachine; i < R; i++) {
		Arr[i] = CArr[i];
	}
}

void One_diffusion(int sero, int garo) {
	for (int i = 0; i < 4; i++) {
		int nextSero = sero + dy[i];
		int nextGaro = garo + dx[i];

		if (!isInside(nextSero, nextGaro)) continue;
		if (Arr[nextSero][nextGaro].first == -1) continue;

		int diffusionValue = Arr[sero][garo].first / 5;
		Arr[nextSero][nextGaro].second += diffusionValue;
		Arr[sero][garo].second -= diffusionValue;
	}
}

void All_diffusion() {
	for (int i = 0; i < R; i++) {
		for (int k = 0; k < C; k++) {
			if (Arr[i][k].first > 0) {
				One_diffusion(i, k);
			}
		}
	}
	for (int i = 0; i < R; i++) {
		for (int k = 0; k < C; k++) {
			if (Arr[i][k].first != -1) {
				Arr[i][k].first += Arr[i][k].second;
				Arr[i][k].second = 0;
				if (Arr[i][k].first < 0) Arr[i][k].first = 0;
			}
		}
	}
}

void GameStart() {
	for (int i = 0; i < T; i++) {
		All_diffusion();
		RotateUp();
		RotateDown();
	}
}

int main(void) {
	Input();
	GameStart();
	cout <<allDustCount-Result;
}

설명

• 입력 처리:
  • 행(R), 열(C), 시간(T)을 입력받고, 배열을 초기화한 후 공기청정기 위치를 찾아 저장합니다.
• 공기청정기 순환:
  • RotateUp과 RotateDown 함수는 각각 상단 및 하단 공기청정기의 순환 동작을 시뮬레이션하여 미세먼지를 처리합니다.
• 미세먼지 확산:
  • All_diffusion 함수는 배열 전체의 미세먼지가 확산되는 과정을 처리합니다.
• 시뮬레이션 실행:
  • GameStart 함수는 주어진 시간(T) 동안 확산 및 공기청정기 동작을 반복 실행합니다.

이 프로그램을 통해 주어진 시간 동안의 미세먼지 확산과 공기청정기 작동을 시뮬레이션할 수 있습니다. 최종적으로 남아 있는 미세먼지 양을 출력합니다.