[백준 / C++] 17144번: 미세먼지 안녕! (삼성 SW 역량 테스트 기출)

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

17144번: 미세먼지 안녕!

 

난이도: solved.ac 골드 4

 

구현 방법

각 1초 동안 진행되는 과정은 T를 1씩 줄여나가며 T가 0이 될 때까지 진행해주었다.

(while(T--) {...} 방식으로)

 

미세먼지를 확산하는 과정에서 확산으로 인한 값의 변화 때문에 미세먼지 상태를 나타내는 배열은 단 하나만으로는 부족한데, 따라서 배열을 두 개 이용했다.

 

각 확산된 값을 임시 배열에 저장했다가 다시 원래 배열로 복사하는 식으로 구현하면 시간복잡도가 조금 더 커질 것 같아서 배열 두 개를 번갈아가며 사용했는데, 무슨 말이냐면

 

결과적으로, T가 짝수일 때는 board_even이라는 배열, T가 홀수일 때는 board_odd라는 배열에 미세먼지가 확산된 상태를 저장했다.

 

1초가 지나면 짝수였던 T는 홀수가 되어 board_even에 있던 정보를 이용해 확산된 정보를 board_odd에 바로 저장하고, T가 이전에 홀수였다면 짝수가 되므로 board_odd에 있던 정보를 이용해 board_even에 곧바로 저장해서 배열을 매번 복사하는 필요성을 없앴다.

 

회전하는 과정은 공기청정기의 위쪽 좌표와 아래쪽 좌표를 각각 up과 down이라는 변수에 저장해 up 위쪽 부분과 down 아래쪽 부분을 각각 회전시키는 방식으로 구현했다.

 

회전하는 과정에서 실수가 있을 수 있으니 조심해야 한다.

(본인 이야기...ㅠ)

 

코드

#include <bits/stdc++.h>
using namespace std;
int dy[4] = { 1,0,-1,0 }, dx[4] = { 0,1,0,-1 };
int board_odd[50][50], board_even[50][50];
int R, C, T, up, down;
void transmit(int y, int x);

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> R >> C >> T;
	int ans = 0, num, i, j;
	bool flg = 0;
	for (i = 0; i < R; i++) {
		for (j = 0; j < C; j++) {
			cin >> num;
			// T가 홀수면 odd, 짝수면 even에 저장
			if (T % 2)
				board_odd[i][j] = num;
			else
				board_even[i][j] = num;
			if (num == -1) {
				if (!flg) {
					up = i;
					down = i + 1;
					flg = 1;
				}
			}
		}
	}
	while (T--) {
		// T가 홀수면 even을 이용해 odd에 저장, 짝수면 odd를 이용해 even에 저장
		for (i = 0; i < R; i++) {
			for (j = 0; j < C; j++) {
				// 전이
				if (T % 2 && board_even[i][j] > 0)
					transmit(i, j);
				else if (!(T % 2) && board_odd[i][j] > 0)
					transmit(i, j);
			}
		}
		// 회전
		if (T % 2) {
			// 반시계 방향
			for (i = up - 2; i >= 0; i--)
				board_odd[i + 1][0] = board_odd[i][0];
			for (j = 1; j < C; j++)
				board_odd[0][j - 1] = board_odd[0][j];
			for (i = 1; i < up + 1; i++)
				board_odd[i - 1][C - 1] = board_odd[i][C - 1];
			for (j = C - 2; j > 0; j--)
				board_odd[up][j + 1] = board_odd[up][j];
			board_odd[up][1] = 0;
			// 시계 방향
			for (i = down + 2; i < R; i++)
				board_odd[i - 1][0] = board_odd[i][0];
			for (j = 1; j < C; j++)
				board_odd[R - 1][j - 1] = board_odd[R - 1][j];
			for (i = R - 2; i > down - 1; i--)
				board_odd[i + 1][C - 1] = board_odd[i][C - 1];
			for (j = C - 2; j > 0; j--)
				board_odd[down][j + 1] = board_odd[down][j];
			board_odd[down][1] = 0;
		}
		else {
			// 반시계 방향
			for (i = up - 2; i >= 0; i--)
				board_even[i + 1][0] = board_even[i][0];
			for (j = 1; j < C; j++)
				board_even[0][j - 1] = board_even[0][j];
			for (i = 1; i < up + 1; i++)
				board_even[i - 1][C - 1] = board_even[i][C - 1];
			for (j = C - 2; j > 0; j--)
				board_even[up][j + 1] = board_even[up][j];
			board_even[up][1] = 0;
			// 시계 방향
			for (i = down + 2; i < R; i++)
				board_even[i - 1][0] = board_even[i][0];
			for (j = 1; j < C; j++)
				board_even[R - 1][j - 1] = board_even[R - 1][j];
			for (i = R - 2; i > down - 1; i--)
				board_even[i + 1][C - 1] = board_even[i][C - 1];
			for (j = C - 2; j > 0; j--)
				board_even[down][j + 1] = board_even[down][j];
			board_even[down][1] = 0;
		}
		// 0으로 초기화
		if (T % 2) {
			for (i = 0; i < R; i++)
				memset(board_even[i], 0, sizeof(int) * C);
		}
		else {
			for (i = 0; i < R; i++)
				memset(board_odd[i], 0, sizeof(int) * C);
		}
	}
	for (i = 0; i < R; i++)
		for (j = 0; j < C; j++)
			if (board_even[i][j] > 0)
				ans += board_even[i][j];
	cout << ans;
}

void transmit(int y, int x) {
	if (T % 2)
		board_odd[y][x] += board_even[y][x];
	else
		board_even[y][x] += board_odd[y][x];
	int cnt = 0;
	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (ny < 0 || ny >= R || nx < 0 || nx >= C)
			continue;
		if ((ny == up && nx == 0) || (ny == down && nx == 0))
			continue;
		if (T % 2)
			board_odd[ny][nx] += (board_even[y][x] / 5);
		else
			board_even[ny][nx] += (board_odd[y][x] / 5);
		cnt++;
	}
	if (T % 2)
		board_odd[y][x] -= ((board_even[y][x] / 5) * cnt);
	else
		board_even[y][x] -= ((board_odd[y][x] / 5) * cnt);
}

 

성능

코드 제출 결과