본문 바로가기
programming/알고리즘 풀이

[백준 알고리즘] 17144번 - 미세먼지 안녕!

AGAPE1225 2023. 6. 30. 19:16
반응형

1. 문제 및 예시 실행결과

 

 구현과 시뮬레이션 문제이다. 어우 힘들어... 구현은 아무래도 높은 집중력과 예외처리를 위한 설계가 중요시 되는 것 같다. 한번 오류나면 멘탈이 나가서 문제 난이도가 생각보다 높게 느껴진다. 재능있는 사람들은 처음부터 오류없는 코드를 잘 작성하겠지만, 나는 그런 것 같지는 않으니 최대한 고심해서 코드를 짠다. 그래서 이리 힘든 것인지...

 

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

 

17144번: 미세먼지 안녕!

미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사

www.acmicpc.net

2. 풀이 과정

 

 알고리즘 책에서 배운 가장 큰 한가지가 있다면 문제를 쪼개는 것. 그래서 나름 문제를 쪼개서 알고리즘을 작성해보았다.

 

1. 미세먼지 확산

2. 공기청정기 가동

 

 별거 아니지만 이대로 함수를 작성 해보았다. 작성한 함수는 다음과 같다.

 

int main(void) {

	cin >> R >> C >> T;

	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			cin >> house[i][j];
		}
	}

	for (int i = 0; i < T; i++) {
		diffusion();
		air_cleaner();
	}

	cout << get_fine_dust();

	return 0;
}

 

diffusion() 함수는 미세먼지, air_cleaner()는 공기청정기 가동이다. 함수로 만든 이유는 그냥 나를 위해서다. 가끔 동기들이 이런 구현 문제는 직관력이 뛰어난 말 그대로 피지컬이 좋은 사람들이 유리하다고 하는데, 나는 그렇지 않다. 그래서 코드를 최대한 나눠 정리하는 것을 선호한다.

 

 일단 diffusion() 함수의 작성은 나름 간단했다. 주의해야할점은 퍼지는 미세먼지의 값에 변화가 있으면 안되기에 배열을 하나 더 선언 한 것이다. 다음은 내가 구현한 함수이다.

 

void diffusion() {
	int tmp[50][50] = { 0 };

	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {

			if (house[i][j] == -1)
				tmp[i][j] = -1;

			else if (house[i][j] > 0) {

				int count = 0;

				for (int k = 0; k < 4; k++) {
					
					int tmp_row = i + dir_x[k];
					int tmp_col = j + dir_y[k];

					if (check_range(tmp_row, tmp_col) && 
						house[tmp_row][tmp_col] != -1) {

						count++;
						tmp[tmp_row][tmp_col] += house[i][j] / 5;
					}
				}
				tmp[i][j] += house[i][j] - ((house[i][j] / 5) * count);
			}
		}
	}

	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			house[i][j] = tmp[i][j];
		}
	}
}

 

 house 배열은 전역변수로 선언하였다. 자 그럼 공기청정기를 가동시켜보자.

 

사실 공기 청정기를 가동시키는 것도 쪼갤 수 있다. 다음과 같은 순서일 것이다.

 

1. 위쪽 라인의 미세먼지 오른쪽으로 밀기

2. 위쪽 라인의 미세먼지 위쪽으로 밀기

3. 위쪽 라인의 미세먼지 왼쪽으로 밀기

4. 위쪽 라인의 미세먼지 아래쪽으로 밀기

 

// 아래쪽도 똑같이 실행.

 

하지만 마지막 값들이 변하기 때문에 순서를 역순으로 실행해야 한다. 그래서 내가 작성한 함수는 다음과 같다.

 

void air_cleaner() {

	int up_row, down_row;

	//시작 위치 구하기
	for (int i = 0; i < R; i++) {
		if (house[i][0] == -1) {
			up_row = i;
			down_row = i + 1;
			break;
		}
	}

	//위쪽 공기 청정기
	moving_down(0, 0, up_row);
	moving_left(0, C - 1);
	moving_up(up_row, C - 1, 0);
	moving_right(up_row);

	//아래쪽 공기 청정기
	moving_up(R - 1, 0, down_row);
	moving_left(R - 1, C - 1);
	moving_down(down_row, C - 1, up_row);
	moving_right(down_row);

	house[up_row][0] = -1;
	house[down_row][0] = -1;

}

 

시작 위치를 구하고 넘겨주는 값을 기준으로 시작하는 네방향의 함수들을 호출한다. 마지막으로 방향 함수만을 작성하면 된다. 다음과 같다.

 

void moving_right(int start_row) {
	
	int tmp[50] = { 0 };

	for (int i = 1; i < C - 1; i++) {
		tmp[i + 1] = house[start_row][i];
	}
	for (int i = 1; i < C; i++) {
		house[start_row][i] = tmp[i];
	}
}

void moving_up(int start_row, int start_col, int conditional) {
	int tmp[50] = { 0 };
	int max = 0;

	if (start_col == 0) {
		max = conditional - 1;
	}
	for (int i = start_row; i > max; i--) {
		tmp[i - 1] = house[i][start_col];
	}
	for (int i = start_row; i >= max; i--) {
		house[i][start_col] = tmp[i];
	}
}

void moving_left(int start_row, int start_col) {
	int tmp[50] = { 0 };
	for (int i = start_col; i > 0; i--) {
		tmp[i - 1] = house[start_row][i];
	}
	for (int i = start_col; i >= 0; i--) {
		house[start_row][i] = tmp[i];
	}
}

void moving_down(int start_row, int start_col, int conditional) {
	int tmp[50] = { 0 };
	int max = R;

	if (start_row == 0) {
		max = conditional;
	}

	for (int i = start_row; i < max - 1; i++) {
		tmp[i + 1] = house[i][start_col];
	}
	for (int i = start_row; i < max; i++) {
		house[i][start_col] = tmp[i];
	}

}

bool check_range(int r, int c) {
	if (r < 0 || r >= R || 
		c < 0 || c >= C)
		return false;
	return true;
}

 

최종 코드는 다음과 같다.

 

#include <iostream>

using namespace std;

int house[50][50] = { 0 };
int R, C, T;
int dir_x[4] = { 0, 1, 0, -1 };
int dir_y[4] = { 1, 0, -1, 0 };

void moving_right(int start_row) {
	
	int tmp[50] = { 0 };

	for (int i = 1; i < C - 1; i++) {
		tmp[i + 1] = house[start_row][i];
	}
	for (int i = 1; i < C; i++) {
		house[start_row][i] = tmp[i];
	}
}

void moving_up(int start_row, int start_col, int conditional) {
	int tmp[50] = { 0 };
	int max = 0;

	if (start_col == 0) {
		max = conditional - 1;
	}
	for (int i = start_row; i > max; i--) {
		tmp[i - 1] = house[i][start_col];
	}
	for (int i = start_row; i >= max; i--) {
		house[i][start_col] = tmp[i];
	}
}

void moving_left(int start_row, int start_col) {
	int tmp[50] = { 0 };
	for (int i = start_col; i > 0; i--) {
		tmp[i - 1] = house[start_row][i];
	}
	for (int i = start_col; i >= 0; i--) {
		house[start_row][i] = tmp[i];
	}
}

void moving_down(int start_row, int start_col, int conditional) {
	int tmp[50] = { 0 };
	int max = R;

	if (start_row == 0) {
		max = conditional;
	}

	for (int i = start_row; i < max - 1; i++) {
		tmp[i + 1] = house[i][start_col];
	}
	for (int i = start_row; i < max; i++) {
		house[i][start_col] = tmp[i];
	}

}

bool check_range(int r, int c) {
	if (r < 0 || r >= R || 
		c < 0 || c >= C)
		return false;
	return true;
}

void diffusion() {
	int tmp[50][50] = { 0 };

	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {

			if (house[i][j] == -1)
				tmp[i][j] = -1;

			else if (house[i][j] > 0) {

				int count = 0;

				for (int k = 0; k < 4; k++) {
					
					int tmp_row = i + dir_x[k];
					int tmp_col = j + dir_y[k];

					if (check_range(tmp_row, tmp_col) && 
						house[tmp_row][tmp_col] != -1) {

						count++;
						tmp[tmp_row][tmp_col] += house[i][j] / 5;
					}
				}
				tmp[i][j] += house[i][j] - ((house[i][j] / 5) * count);
			}
		}
	}

	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			house[i][j] = tmp[i][j];
		}
	}
}

void air_cleaner() {

	int up_row, down_row;

	//시작 위치 구하기
	for (int i = 0; i < R; i++) {
		if (house[i][0] == -1) {
			up_row = i;
			down_row = i + 1;
			break;
		}
	}

	//위쪽 공기 청정기
	moving_down(0, 0, up_row);
	moving_left(0, C - 1);
	moving_up(up_row, C - 1, 0);
	moving_right(up_row);

	//아래쪽 공기 청정기
	moving_up(R - 1, 0, down_row);
	moving_left(R - 1, C - 1);
	moving_down(down_row, C - 1, up_row);
	moving_right(down_row);

	house[up_row][0] = -1;
	house[down_row][0] = -1;

}

int get_fine_dust() {

	int count = 0;
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			if(house[i][j] != -1)
				count += house[i][j];
		}
	}
	return count;

}

int main(void) {

	cin >> R >> C >> T;

	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			cin >> house[i][j];
		}
	}

	for (int i = 0; i < T; i++) {
		diffusion();
		air_cleaner();
	}

	cout << get_fine_dust();

	return 0;
}

 

반응형

'programming > 알고리즘 풀이' 카테고리의 다른 글

[백준 알고리즘] 14938번 - 서강그라운드  (3) 2023.07.03
[백준 알고리즘] 12851번 - 숨바꼭질 2 (BFS에서의 같은 depth 처리과정)  (0) 2023.07.03
[프로그래머스] 138476번 - 귤고르기  (5) 2023.04.01
[프로그래머스] 86491번 - 최소직사각형 (완전탐색)  (3) 2023.03.09
[백준 알고리즘] 1744번 - 수 묶기 (그리디 알고리즘)  (0) 2021.08.06

'programming/알고리즘 풀이' Related Articles

티스토리툴바