[백준 / C++] 16234번: 인구 이동 (BFS 풀이)

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

16234번: 인구 이동

 

난이도: solved.ac 골드 4

 

알고리즘 분류

구현, 그래프 탐색, 너비 우선 탐색(BFS), 시물레이션

 

아이디어

DFS 또는 BFS로 풀 수 있는 문제다.

 

나는 아래의 과정을 통해 구현했다.

1. 한 곳을 기준으로 BFS를 돌린다.
2. 방문한 곳에서는 아래의 과정을 수행한다.
   - visited = 1로 만든다.
   - 인구의 수를 sum에 더한다.
   - 연합된 나라의 수를 센다.
   - 연합된 나라의 좌표를 저장한다.
3. 상하좌우에서 L이상 R이하인 곳으로 이동한다.
4. 한 곳의 BFS 탐색이 끝나면 저장했던 연합된 나라의 좌표들을 바탕으로 board 값을 수정한다.
5. 모든 좌표를 탐색했다면 모든 좌표의 visited = 0으로 초기화한다.

 

나는 연합된 나라를 큐에 저장해서 좌표를 하나씩 pop을 하는 식으로 구현했다.

그랬더니 아래처럼 시간이 상대적으로 오래 걸렸는데

코드 제출 결과

 

다른 분의 코드를 보니 그냥 벡터로 저장하고 원소 하나씩 이동하는 식으로 구현했길래 나도 그렇게 해보았다.

그렇게 하니 400ms대로 단축되었다.

코드 제출 결과

 

코드

큐로 구현

#include <bits/stdc++.h>
using namespace std;
// 백준 16234번: 인구 이동 (골드 4)
int board[50][50];
bool visited[50][50];
int dy[4] = { 0,1,0,-1 }, dx[4] = { 1,0,-1,0 };
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int N, L, R, i, j, ans = 0;
	cin >> N >> L >> R;
	for (i = 0; i < N; i++)
		for (j = 0; j < N; j++)
			cin >> board[i][j];
	bool flg = 1;	// 인구 이동이 일어나는지 표시
	while (flg) {
		flg = 0;	// 인구 이동이 일어나지 않는다고 가정
		for (i = 0; i < N; i++) {
			for (j = 0; j < N; j++) {
				// 아직 방문하지 않은 곳을 기준으로 BFS 탐색
				if (!visited[i][j]) {
					queue<pair<int, int>> q;	// BFS에 사용할 큐
					queue<pair<int, int>> coord;	// 인구 이동이 일어나는 좌표를 저장
					q.push({ i,j });
					coord.push({ i,j });
					visited[i][j] = 1;
					int area = 1;	// 방문한 나라(좌표)의 개수 (연합을 이루고 있는 칸의 개수)
					int sum = board[i][j];	// 연합의 인구수
					while (!q.empty()) {
						int cury = q.front().first;
						int curx = q.front().second;
						q.pop();
						int curp = board[cury][curx];
						for (int dir = 0; dir < 4; dir++) {
							int ny = cury + dy[dir];
							int nx = curx + dx[dir];
							if (ny < 0 || ny >= N || nx < 0 || nx >= N)
								continue;
							// 국경선을 열 수 있을 때
							if (abs(board[ny][nx] - curp) >= L && abs(board[ny][nx] - curp) <= R && !visited[ny][nx]) {
								q.push({ ny,nx });
								coord.push({ ny,nx });
								area++;
								sum += board[ny][nx];
								visited[ny][nx] = 1;
							}
						}
					}
					// area가 2 이상이면 인구 이동이 일어났으므로 flg를 1로 바꿔줌
					if (area > 1)
						flg = 1;
					int np = sum / area;	// 인구 이동이 일어난 후의 각 나라별 인구수
					while (!coord.empty()) {
						int y = coord.front().first;
						int x = coord.front().second;
						coord.pop();
						board[y][x] = np;	// 인구수 업데이트
					}
				}
			}
		}
		if (flg)
			ans++;	// 인구 이동이 일어났을 경우
		// visited를 모두 0으로 초기화
		for (i = 0; i < N; i++)
			memset(visited[i], 0, sizeof(bool) * N);
	}
	cout << ans << "\n";
}

벡터로 구현

#include <bits/stdc++.h>
using namespace std;
// 백준 16234번: 인구 이동 (골드 4)
int board[50][50];
bool visited[50][50];
int dy[4] = { 0,1,0,-1 }, dx[4] = { 1,0,-1,0 };
vector<pair<int, int>> coord;	// 인구 이동이 일어나는 좌표를 저장

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int N, L, R, i, j, ans = 0;
	cin >> N >> L >> R;
	for (i = 0; i < N; i++)
		for (j = 0; j < N; j++)
			cin >> board[i][j];
	bool flg = 1;	// 인구 이동이 일어나는지 표시
	while (flg) {
		flg = 0;	// 인구 이동이 일어나지 않는다고 가정
		for (i = 0; i < N; i++) {
			for (j = 0; j < N; j++) {
				// 아직 방문하지 않은 곳을 기준으로 BFS 탐색
				if (!visited[i][j]) {
					coord.clear();
					queue<pair<int, int>> q;	// BFS에 사용할 큐
					q.push({ i,j });
					coord.push_back({ i,j });
					visited[i][j] = 1;
					int area = 1;	// 방문한 나라(좌표)의 개수 (연합을 이루고 있는 칸의 개수)
					int sum = board[i][j];	// 연합의 인구수
					while (!q.empty()) {
						int cury = q.front().first;
						int curx = q.front().second;
						q.pop();
						int curp = board[cury][curx];
						for (int dir = 0; dir < 4; dir++) {
							int ny = cury + dy[dir];
							int nx = curx + dx[dir];
							if (ny < 0 || ny >= N || nx < 0 || nx >= N)
								continue;
							// 국경선을 열 수 있을 때
							if (abs(board[ny][nx] - curp) >= L && abs(board[ny][nx] - curp) <= R && !visited[ny][nx]) {
								q.push({ ny,nx });
								coord.push_back({ ny,nx });
								area++;
								sum += board[ny][nx];
								visited[ny][nx] = 1;
							}
						}
					}
					// area가 2 이상이면 인구 이동이 일어났으므로 flg를 1로 바꿔줌
					if (area == 1)
						continue;
					flg = 1;
					int np = sum / area;	// 인구 이동이 일어난 후의 각 나라별 인구수
					// 인구수 업데이트
					for (auto c : coord)
						board[c.first][c.second] = np;
				}
			}
		}
		if (flg)
			ans++;	// 인구 이동이 일어났을 경우
		// visited를 모두 0으로 초기화
		memset(visited, 0, sizeof(visited));
	cout << ans;
}