백준 알고리즘 17144_미세먼지 안녕 C

문제

(링크)17144번: 미세먼지 안녕! (acmicpc.net)

17144번: 미세먼지 안녕!

 

사고과정

문제에서 요구하는대로 먼지확산 -> 공기순환의 과정만 조건대로 구현하면 된다. 그래서 사용한 함수는 2개! 처음엔 탐색횟수를 줄이기 위해 먼지의 위치를 저장하는 배열을 만들까 했는데, 빈공간으로도 먼지가 확산되기 때문에 map전체를 탐색하는 것이 마음이 편할 것 같았다. 

 

내코드

#include <stdio.h>
#include <stdlib.h>
#define FRESHER -1


int width, height, time;
int dx[4] = {0,1,0,-1};//clockwise
int dy[4] = {-1,0,1,0};
int fresher[2];

void diffusion(int** map) {
	int** temp = (int**)calloc(height, sizeof(int*));
	for (int i = 0; i < height; i++) {
		temp[i] = (int*)calloc(width, sizeof(int));
	}

	for (int i = 0; i < height; i++) {
		for (int j = 0; j < width; j++) {
			if (map[i][j] > 0) {//if dust exist
				int count = 0;
				for (int k = 0; k < 4; k++) {
					int X = j + dx[k];
					int Y = i + dy[k];
					if (X >= 0 && X < width && Y >= 0 && Y < height) {
						if (map[Y][X] != FRESHER) {
							temp[Y][X] += (map[i][j] / 5);
							count++;
						}
					}
				}
				map[i][j] -= count * (map[i][j] / 5);
			}
		}
	}

	for (int i = 0; i < height; i++) {
		for (int j = 0; j < width; j++) {
			map[i][j] += temp[i][j];
		}
	}
	for (int i = 0; i < height; i++) {
		free(temp[i]);
	}
	free(temp);
}

void Fresh(int** map) {
	int x = 0;
	int y = fresher[0];//top
	int dir = 0;
	y += dy[dir];
	while (dir < 4) {
		int X = x + dx[dir];
		int Y = y + dy[dir];
		if (dir==3 && map[Y][X] == FRESHER) {
			map[y][x] = 0;
			break;
		}

		if (X >= 0 && X < width && Y >= 0 && Y <= fresher[0]) {
			map[y][x] = map[Y][X];
			y = Y;
			x = X;
		}
		else dir++;
	}
	
	
	x = 0;
	y = fresher[1];//bottom
	dir = 0;
	y -= dy[dir];
	while (dir < 4) {
		int Y, X;
		if (dir % 2 == 1) {
			Y = y + dy[dir];
			X = x + dx[dir];
		}
		else {
			Y = y - dy[dir];
			X = x - dx[dir];
		}

		if (dir==3&& map[Y][X] == FRESHER) {
			map[y][x] = 0;
			break;
		}

		if (X >= 0 && X < width && Y >= fresher[1] && Y < height) {
			map[y][x] = map[Y][X];
			y = Y;
			x = X;
		}
		else dir++;
	}

}

int main() {
	int i, j;
	scanf_s("%d %d %d", &height, &width, &time);
	int** map = (int**)malloc(height * sizeof(int*));
	for (i = 0; i < height; i++) {
		map[i] = (int*)malloc(width * sizeof(int));
	}
	int f = 0;
	for (i = 0; i < height; i++) {
		for (j = 0; j < width; j++) {
			scanf_s("%d", &map[i][j]);
			if (map[i][j] == FRESHER)fresher[f++] = i;
		}
	}

	while (time > 0) {
		diffusion(map);
		Fresh(map);
		time--;
	}

	int answer = 0;
	for (i = 0; i < height; i++) {
		for (j = 0; j < width; j++) {
			if (map[i][j] > 0) {
				answer += map[i][j];
			}
		}
	}
	printf("%d", answer);

	for (i = 0; i < height; i++) {
		free(map[i]);
	}
	free(map);
	return 0;
}

먼저 diffusion함수는 먼지를 현재 위치로부터 4방향으로 확산시키는 역할을 한다. map의 먼지가 있는 각 위치에서 4방향을 탐색하는데, map의 범위 안이고 공기청정기가 없는 곳에, 자신의 먼지양/5를 퍼트린다. 이때 주의해야할 점은 매 순간 먼지를 네 방향으로 확산시키면, 나중에 확산되는 먼지는 원래 양보다 많아질 수 있다. 그러므로 탐색 모든 map을 탐색한 이후에 확산된 먼지를 각 위치에 추가해야한다.

다음은 Fresh함수이다. 이 지금까지 많이 해온 치환 함수이다. map을 반으로 갈라 시계/반시계방향으로 탐색치환하면된다.  

 

피드백

진짜 바보같은 실수를 했다. fresh함수에서 60번쨰 줄과 89번쨰 줄의 조건에서 fresher[0]과 fresher[1]을 height과 0으로 하여 map전체를 순환시켰다. 검토할 때 코드의 의미를 생각하며 할 것