[BOJ-16234] 인구이동

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

16234번: 인구 이동

 

2017년 하반기 모 기업 코딩테스트 문제입니다.

 

더 이상 인구 이동이 없을 때까지 지속된다는 반복 조건을 처리해주는 것에 대한 경험이 없어서 문제 푸는데 꽤 오랜 시간이 걸렸습니다.(결국엔 그냥 루프 하나를 주고 문제 그대로 이동하지 않으면 반복문을 break 해주면 되는 거였음..)

 

저같은 경우, 시험장에서 긴장했을 경우 + 문제 이해 시간 등을 고려하면 아마 3시간 동안 1문제만 풀고 나왔을것 같습니다..

 

-문제 풀이

1. 문제에서 입력으로 주어지는 것들을 입력받습니다.

 

2. 인구 이동을 계속 시킬 루프 하나를 만들어 줍니다.

 

3. 만들어준 루프 안에 모든 나라를 방문해야 하기 때문에 2중 for문을 만들고 방문하지 않은 나라들을 방문해줍니다.

 

4. 그 다음, 방문 체크를 해주고 방문한 나라의 좌표를 큐에 넣은 뒤 bfs 탐색을 시작합니다.

 

5. 문제에서 인구 차이의 조건을 인접한 나라와 인구 차이가 L명 이상 R명 이하일 경우 국경선을 공유한다고 했으므로 상, 하, 좌, 우로 인접한 나라와 인구 차이를 구하고 해당 조건을 만족시킬때, 큐에 넣어줍니다.

 

6. 현재 큐에 들어가는 나라들은 인접한 나라이면서 연합을 이루는 나라이므로 이 연합의 합과 연합인 나라의 수를 따로 배열을 만들어 저장해줍니다.

 

7. 현재 2중 for문이 끝나면 인구이동을 완료했으므로 이동한 인구를 새로 map에 넣어줍니다.

 

8. 3 ~ 7번 과정을 인구 이동이 없을 때 까지 반복하고 인구 이동이 없을 경우 res 값을 출력해줍니다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <queue>

using namespace std;

struct POSITION {
	int y, x;
};
int n, l, r, res;
int map[50][50];
const int dy[] = { -1,1,0,0 };
const int dx[] = { 0,0,-1,1 };
queue<POSITION> q;

int main(void) {

	scanf("%d %d %d", &n, &l, &r);

	for (int y = 0; y < n; y++) {
		for (int x = 0; x < n; x++) {
			scanf("%d", &map[y][x]);
		//	q.push({ y,x });
		}
	}

	bool flag = true;

	while (flag) {
		flag = false;

		int visited[50][50] = { 0, };
		int union_cnt[2501] = { 0, };
		int union_sum[2501] = { 0, };
		int cnt = 0;

		for (int y = 0; y < n; y++){
			for (int x = 0; x < n; x++) {
				visited[y][x] = -1;
			}
		}
		for (int y = 0; y < n; y++) {
			for (int x = 0; x < n; x++) {
				if (visited[y][x] == -1) {
					union_cnt[cnt] += 1;
					union_sum[cnt] += map[y][x];
					visited[y][x] = cnt;
					q.push({ y,x });

					while (!q.empty()) {
						POSITION cur = q.front(); q.pop();

						for (int dir = 0; dir < 4; dir++) {
							POSITION next;

							next.y = cur.y + dy[dir];
							next.x = cur.x + dx[dir];

							if (next.y < 0 || next.y >= n || next.x < 0 || next.x >= n) continue;

							int dif = abs(map[next.y][next.x] - map[cur.y][cur.x]);
							if (l <= dif && dif <= r && visited[next.y][next.x] == -1) {
								flag = true;
								visited[next.y][next.x] = cnt;
								union_sum[cnt] += map[next.y][next.x];
								union_cnt[cnt] += 1;
								q.push(next);
							}
						}
					}
				}
				cnt += 1;
			}
		}

		for (int y = 0; y < n; y++) {
			for (int x = 0; x < n; x++) {
				if (visited[y][x] != -1) {
					map[y][x] = (union_sum[visited[y][x]] / union_cnt[visited[y][x]]);
				}
			}
		}
		if (flag) {
			res += 1;
		}
	}

	printf("%d", res);

	getchar();
	getchar();

	return 0;
}