[백준[ 16234번: 인구 이동

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

16234번: 인구 이동

문제 이해

1. 국경을 열었다가 (만약 열린 국경이 하나도 없으면 더이상 조정이 일어나지 않으므로 끝낸다)

2. 연합국을 찾고 (모든 칸이 visit될 때까지 BFS)

3. 연합국 인구 평균을 연합국 모든 칸에 넣어주고 (만약 변경이 하나도 없으면 끝낸다)

4. 국경을 닫는다

 

Open_Border()

국경을 여는 것은 모든 칸에 대해 4방향 탐색을 하고 인구 차가 범위 내이면 open[i][j][방향] = 1 해서 이쪽 벽을 허물어준다고 표시하면 된다.

int Open_Border(void) {
	int opened = 0; 
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			for (int k = 0; k < 4; k++) {
				int ny = i + dy[k];
				int nx = j + dx[k];
				if (ny < 0 || ny >= N || nx < 0 || nx >= N) continue;
				int diff = ABS(map[i][j] - map[ny][nx]);
				if (diff >= L && diff <= R) {
					open[i][j][k] = 1;
					opened = 1;
				}
			}
		}
	}
	return opened;
}

opened라는 변수로 하나라도 국경을 열게 되면 이를 1로 바꿔서 반환하도록 했다. 

이후에 이 함수에 대한 리턴값이 0이면 국경을 하나도 열지 않았다는 뜻이므로 루프에서 break해주면 된다.

 

Find_Union()

• 모든 칸이 방문처리될 때까지 BFS를 돌린다. 
• BFS에서 open[i][j][방향] == 0 이면 갈 수 없는 것으로 처리한다.
• BFS에서 그 연합의 평균을 구해주고, 이를 unions 라는 배열에 인구 평균을 저장해준다. 

int BFS(int sy, int sx, int no) {
	int sum = 0;
	int cnt = 0;
	wp = rp = 0;

	enq(sy, sx);
	visited[sy][sx] = no;
	sum += map[sy][sx];
	cnt++;

	while (!empty()) {
		ELE cur = deq();
		for (int i = 0; i < 4; i++) {
			int ny = cur.y + dy[i];
			int nx = cur.x + dx[i];
			if (ny < 0 || ny >= N || nx < 0 || nx >= N) continue;
			if (visited[ny][nx] != 0) continue;
			if (open[cur.y][cur.x][i] == 0) continue;
			// 갈 수 있음
			enq(ny, nx);
			visited[ny][nx] = no;
			sum += map[ny][nx];
			cnt++;
		}
	}

	int result = sum / cnt;
	return result;
}

void Find_Unions(void) {
	int ucnt = 0;
	memset(unions, 0, sizeof(unions));
	memset(visited, 0, sizeof(visited));
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (visited[i][j] !=0) continue;
			int n = BFS(i, j, ucnt + 1);
			unions[ucnt+1] = n;
			ucnt++;
		}
	}
}

Adjust_Population()

그냥 unions(i번 연합의 인구 평균 저장)에 저장된 값을 visited에 있는 값들을 참고해 (visited에는 몇 번 연합소속인지 있으니까) map 값을 변경하면 된다. 

 

작성 코드

#include <stdio.h>
#include <string.h>
#define MAXN 50
#define ABS(x) (((x)>0)?x:-(x))
int map[MAXN + 5][MAXN + 5];
int visited[MAXN + 5][MAXN + 5];
int N, L, R;
int open[MAXN + 5][MAXN + 5][4];
int unions[MAXN * MAXN + 10];

// 동서남북
int dy[] = { 0, 0, 1, -1 };
int dx[] = { 1, -1, 0, 0 };


void Close_Border(void) {
	memset(open, 0, sizeof(open));
}

void Get_Input(void) {
	scanf("%d %d %d", &N, &L, &R);
	for (int i = 0; i < N; i++) {
		for(int j = 0; j<N; j++){
			scanf("%d", &map[i][j]);
		}
	}
	Close_Border();
}

int Open_Border(void) {
	int opened = 0; 
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			for (int k = 0; k < 4; k++) {
				int ny = i + dy[k];
				int nx = j + dx[k];
				if (ny < 0 || ny >= N || nx < 0 || nx >= N) continue;
				int diff = ABS(map[i][j] - map[ny][nx]);
				if (diff >= L && diff <= R) {
					open[i][j][k] = 1;
					opened = 1;
				}
			}
		}
	}
	return opened;
}


typedef struct st {
	int y, x;
}ELE;
ELE q[MAXN * MAXN * 10];
int wp, rp;
void enq(int y, int x) {
	q[wp].y = y, q[wp++].x = x;
}
ELE deq(void) { return q[rp++]; }
int empty(void) { return wp == rp; }

int BFS(int sy, int sx, int no) {
	int sum = 0;
	int cnt = 0;
	wp = rp = 0;

	enq(sy, sx);
	visited[sy][sx] = no;
	sum += map[sy][sx];
	cnt++;

	while (!empty()) {
		ELE cur = deq();
		for (int i = 0; i < 4; i++) {
			int ny = cur.y + dy[i];
			int nx = cur.x + dx[i];
			if (ny < 0 || ny >= N || nx < 0 || nx >= N) continue;
			if (visited[ny][nx] != 0) continue;
			if (open[cur.y][cur.x][i] == 0) continue;
			// 갈 수 있음
			enq(ny, nx);
			visited[ny][nx] = no;
			sum += map[ny][nx];
			cnt++;
		}
	}

	int result = sum / cnt;
	return result;
}

void Find_Unions(void) {
	int ucnt = 0;
	memset(unions, 0, sizeof(unions));
	memset(visited, 0, sizeof(visited));
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (visited[i][j] !=0) continue;
			int n = BFS(i, j, ucnt + 1);
			unions[ucnt+1] = n;
			ucnt++;
		}
	}
}

int Adjust_Population(void) {
	int flag = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if(map[i][j] != unions[visited[i][j]]){
				map[i][j] = unions[visited[i][j]];
				flag = 1;
			}
		}
	}
	return flag;
}

int main(void) {
	int t;
	Get_Input();
	for (t = 0; t < 2000; t++) {
		if(Open_Border() == 0) break;
		Find_Unions();
		if(!Adjust_Population()) break;
		Close_Border();
	}
	printf("%d", t);
	return 0;
}