백준 알고리즘 16234_인구이동 C

문제

(링크)16234번: 인구 이동 (acmicpc.net)

16234번: 인구 이동

 

사고과정

먼저 생각해야할 것은 현재 각 나라의 인구 상태에서 연합이 만들어질 수 있는가이다. 이후 visit배열에 형성된 연합끼리 정보를 달리한 뒤 인구를 분배하면 된다고 생각했다.

그런데 코드를 짜다보니 굳이 연합이 가능하지 탐색하는 것과, 연합을 만든다음 인구를 분배하는 과정을 분리할 필요가 없다는 것을 깨달았다. 

 

내코드

#include <stdio.h>
#include <stdlib.h>



typedef struct {
	int x, y;
}queue;

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

int abs(int i) {
	if (i < 0) {
		i *= -1;
	}
	return i;
}


int getUnion(int** map, int** visit) {
	queue Q[2500];

	int flag = 0;
	for (int i = 0; i < size; i++) {
		for (int j = 0; j < size; j++) {
			int front = 0, rear = 0,sum=0;
			if (visit[i][j] == 0) {
				Q[rear].x = j;
				Q[rear].y = i;
				visit[i][j] = 1;	//연합되면 visit엔 2이상이 저장됨
				rear++;
				sum += map[i][j];
			}
			while (front < rear) {
				int popX = Q[front].x;
				int popY = Q[front].y;
				front++;

				for (int k = 0; k < 4; k++) {
					int Y = popY + dy[k];
					int X = popX + dx[k];
					if (X >= 0 && X < size && Y >= 0 && Y < size) {
						if (visit[Y][X] == 0) {
							int population_gap = abs(map[popY][popX] - map[Y][X]);
							if (population_gap >= gap1 && population_gap <= gap2) {
								Q[rear].x = X;
								Q[rear].y = Y;
								rear++;
								visit[Y][X] = 1;
								sum += map[Y][X];
							}
						}
					}
				}
			}

			if (rear > 1) {
				flag = 1;
				int new_population = sum / rear;
				for (front = 0; front < rear; front++) {
					int X = Q[front].x;
					int Y = Q[front].y;
					map[Y][X] = new_population;
				}
			}
		}
	}

	return flag;		//연합이 하나도 안생기면 return 0, 하나라도 생기면 return 1
}

void clearMatrix(int** a) {
	for (int i = 0; i < size; i++) {
		for (int j = 0; j < size; j++) {
			a[i][j] = 0;
		}
	}
}

int main() {
	scanf("%d %d %d", &size, &gap1, &gap2);

	int** map = (int**)malloc(size * sizeof(int*));
	int** visit = (int**)calloc(size, sizeof(int*));
	for (int i = 0; i < size; i++) {
		map[i] = (int*)malloc(size * sizeof(int));
		visit[i] = (int*)calloc(size, sizeof(int));
	}

	for (int i = 0; i < size; i++) {
		for (int j = 0; j < size; j++) {
			scanf("%d", &map[i][j]);
		}
	}

	int answer = 0;
	while (getUnion(map, visit)) {
		clearMatrix(visit);
		answer++;
	}



	printf("%d", answer);




	for (int i = 0; i < size; i++) {
		free(map[i]);
		free(visit[i]);
	}
	free(map);
	free(visit);

	return 0;
}

먼저 연합국을 찾을 떈 모든 점(국가)에서 탐색을 해야한다. 이후 visit배열을 사용하여 전형적인 bfs를 이용한다. 각 점에서 탐색을 시작할 때, front와 rear를 초기화 시키고 시작점에서 4방향을 탐색한다. map을 벗어나지 않고, 탐색한적 없으며, 문제의 조건을 만족할 때만 visit한다. 이때, 0으로 초기화된 sum에 각 나라의 인구를 더해준다. queue가 빌때까지 탐색하고난 후, rear가 1보다 크면 위에서 구한 sum을 연합국의 개수로 나눈 뒤, 각 나라에 분배한다.

이후 rear가 1보다 큰적(연합을 만든적)이 있다면 flag를 1로 갱신하여 return한다.

 

피드백

아무래도 전 좌표를 탐색한 뒤 각 좌표에서 4방향을 보고 queue를 계속 새로 갱신하다보니 시간이 84ms나 걸렸다.