백준 17144 미세먼지 안녕! C/C++ 풀이

이 문제는 19년도 삼성 SW 역량테스트 기출 문제이다.

산학 장학생으로 시험 풀러갔던 형이 해당 문제를 풀었다고 알려줬는데, 이 문제가 내가 만났던 첫번째 시뮬레이션 문제였다.

 

'그냥 문제에 있는 것을 재현하는게 풀이라니 어떤 다른 알고리즘이 있는게 아니고..??'

 

하지만 증말 어렵다. 왜 수능형 문제라는지 이해가 감...

 

아래는 풀이이다. 풀이는 다른건 없고 문제에 나와있는 조건을 똑같이 2차원 배열에 구현했고, 미세먼지를 확산시킬 때 확산된 미세먼지의 값이 다른 연산에 영향을 줄 수 있기 때문에 추가로 2차원 배열을 하나 더 만들었다.

 

#include <cstdio>

FILE* in = fopen("input.txt", "r");

int r, c, t;
int map[51][51];
int delay[51][51];
int aircon;

//미세먼지 확산을 구현하기 위한 함수
void diffusion(int i, int j) {
	//공기청정기면 따로 확산하지 않는다.
	if (map[i][j] == -1)
		return;
    //확산될 때마다 기존의 값이 줄어들기 때문에  원본 값을 따로 저장해둔다.
	int val = map[i][j];
    //각각 상하좌우이며 
   	//상하좌 같은 경우에는 공기청정기가 있는 경우도 있기 때문에 이를 고려해서 빼준다.
	if (i > 0 && !(i == aircon+1 && j == 0))
	{
		delay[i - 1][j] += val / 5;
		map[i][j] -= val / 5;
	}
	if (i < (r - 1) && !(i == aircon - 2 && j == 0))
	{
		delay[i + 1][j] += val / 5;
		map[i][j] -= val / 5;
	}
	if (j > 0 && !((i == aircon || i == aircon - 1) && j == 1))
	{
		delay[i][j - 1] += val / 5;
		map[i][j] -= val / 5;
	}
	if (j < (c - 1))
	{
		delay[i][j + 1] += val / 5;
		map[i][j] -= val / 5;
	}
}

//공기청정기를 순환하는 함수
void ventilation(int a, int b) {
	//우선 공기청정기의 상하를 0으로 초기화
	map[a - 1][0] = 0; map[b + 1][0] = 0;
    //반시계
	for (int i = 0; i < a - 1; i++)
	{
		map[a - 1 - i][0] = map[a - 2 - i][0];
	}
	for (int i = 0; i < c - 1; i++)
	{
		map[0][i] = map[0][i+1];
	}
	for (int i = 0; i < a; i++)
	{
		map[i][c-1] = map[i+1][c-1];
	}
	for (int i = 0; i < c - 2; i++)
	{
		map[a][c - 1 - i] = map[a][c - 2 - i];
	}
	map[a][1] = 0;
    //시계
	for (int i = 0; i < r - b - 2; i++)
	{
		map[b + 1 + i][0] = map[b + 2 + i][0];
	}
	for (int i = 0; i < c - 1; i++)
	{
		map[r - 1][i] = map[r - 1][i + 1];
	}
	for (int i = 0; i < r-2-b+1; i++)
	{
		map[r-1-i][c-1] = map[r-2-i][c-1];
	}
	for (int i = 0; i < c - 2; i++)
	{
		map[b][c - 1 - i] = map[b][c - 2 - i];
	}
	map[b][1] = 0;
}

//1초에 일어나는 과정을 합쳐놓은 함수
void round() {
	for (int i = 0; i < r; i++)
	{
		for (int j = 0; j < c; j++)
		{
			diffusion(i, j);
		}
	}
    //확산된 값과 기존의 map에서 확산된거 빼고 줄어든 값을 더해줌 
	for (int i = 0; i < r; i++)
	{
		for (int j = 0; j < c; j++)
		{
			map[i][j] += delay[i][j];
			delay[i][j] = 0;
		}
	}
    //디버깅용
	/*for (int i = 0; i < r; i++)
	{
		for (int j = 0; j < c; j++)
		{
			printf("%d ", map[i][j]);
		}
		printf("\n");
	}*/
	ventilation(aircon - 1, aircon);
}

int main() {
	fscanf(in, "%d %d %d", &r, &c, &t);
	for (int i = 0; i < r; i++)
	{
		for (int j = 0; j < c; j++)
		{
			fscanf(in, "%d", &map[i][j]);
			if (map[i][j] == -1)
				aircon = i;
		}
	}
	for (int i = 0; i < t; i++)
		round();
    // 공기청정기의 경우 -1의 값을 가지기 때문에 각 셀의 총합에 2를 더해줘야 함
	int ans = 2;
	for (int i = 0; i < r; i++)
	{
		for (int j = 0; j < c; j++)
		{
			ans += map[i][j];
		}
	}
	printf("%d\n", ans);
	/*for (int i = 0; i < r; i++)
	{
		for (int j = 0; j < c; j++)
		{
			printf("%d ", map[i][j]);
		}
		printf("\n");
	}*/
	return 0;
}

시뮬레이션류 문제는 if 조건 잘 살펴볼 것. and로 해야하는데 or로 잘못했다가 시간을 꽤 날렸다.