JUST WRITE IT. HomeArchivesTagsCategories
백준 16234번 인구 이동
|AlgorithmBOJ|

#16234. 인구 이동

Problem

Solution

  • BFS

N x N 크기의 배열을 전부 탐색하면서 check표시가 되어있지 않은 부분은 인구 이동이 가능한지 확인 작업이 수행된다.

작업 동안 누적 합과 연합에 포함된 나라 수를 계산해야 한다.

  1. queue가 비어있을 때까지 다음을 수행한다.
  2. 현재 위치에서 4방향 탐색 → 범위체크, 탐색할 위치가 미탐색인지 확인
  3. 탐색 가능하면 누적 합, 나라 수 계산, 종료되지 않게 flag 갱신, queue에 넣어준다.
  4. 만약 나라 수가 1보다 크면 누적합과 사람 수를 따로 저장한다.

위 작업이 끝나면 이제 따로 저장한 누적합과 사람 수를 이용해 N x N 크기의 배열을 바꿔준다. (실질적 인구 이동)

만약 flag가 false 즉, 인구이동이 없다면 종료한다.

  • DFS

BFS보다 훨씬 빠르고 깔끔하며 명료하다. 처음에 BFS로 할 생각을 했던 것은 N x N 크기의 배열 값을 미리 바꾸면 인구 이동에 영향을 미치게 된다는 생각에 코드를 작성했었는데 생각해보니 한 번 탐색이 끝나면(BFS든 DFS든) check 표시 되어 있기에 영향을 주지 않고 한 번 탐색할 때 위치만 미리 벡터에 저장해주면 된다.

BFS 1 Try

  • code
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <queue>
    #include <tuple> 
    using namespace std;
    int N, L, R, idx, ans;
    bool no_end;
    int map[51][51];
    int check[51][51]; // 1, 2, 3
    int val[1251][2]; // 값, 사람 수
    int dx[4] = { -1, 1, 0, 0 };
    int dy[4] = { 0, 0, -1, 1 };
    bool isBound(int x, int y) {
    	if (x > -1 && y > -1 && x < N && y < N) return true;
    	return false;
    }
    void movePeople(int r, int c) {
    	idx++; 
    	int sum = map[r][c], cnt = 1;
    	queue<pair<int, int>> q;
    	q.push({ r, c });
    	check[r][c] = idx;
    	while (!q.empty()) {
    		int x, y;
    		tie(x, y) = q.front();
    		q.pop();
    		for (int dir = 0; dir < 4; ++dir) {
    			int d_x = x + dx[dir];
    			int d_y = y + dy[dir];
    			if (isBound(d_x, d_y) && check[d_x][d_y] == 0) {
    				if (abs(map[x][y] - map[d_x][d_y]) >= L && abs(map[x][y] - map[d_x][d_y]) <= R) {
    					check[d_x][d_y] = idx;
    					q.push({ d_x, d_y });
    					no_end = true;
    					cnt++; sum += map[d_x][d_y];
    				}
    			}
    		}
    	}
    	if (cnt > 1) {
    		val[idx][0] = sum;
    		val[idx][1] = cnt;
    	}
    	else {
    		check[r][c] = 0;
    		idx--;
    	}
    }
    void changePeople() {
    	bool no_move = true;
    	for (int i = 0; i < N; ++i) {
    		for (int j = 0; j < N; ++j) {
    			if (check[i][j] == 0) continue;
    			map[i][j] = val[check[i][j]][0] / val[check[i][j]][1];
    			check[i][j] = 0; no_move = false;
    		}
    	}
    	if (!no_move) ans++;
    }
    int main() {
    	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]);
    		}
    	}
    	do {
    		idx = 0;
    		no_end = false;
    		for (int i = 0; i < N; ++i) {
    			for (int j = 0; j < N; ++j) {
    				if (check[i][j] > 0) continue;
    				movePeople(i, j);
    			}
    		}
    		changePeople();
    	} while (no_end);
    	printf("%d\n", ans);
    	return 0;
    }

    DFS 1 Try

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <vector>
    using namespace std;
    int N, L, R, sum, ans;
    int map[51][51];
    bool check[51][51]; 
    vector<pair<int, int> > v; // 위치 정보
    int dx[4] = { -1, 1, 0, 0 };
    int dy[4] = { 0, 0, -1, 1 };
    bool isBound(int x, int y) {
    	if (x > -1 && y > -1 && x < N && y < N) return true;
    	return false;
    }
    void dfs(int x, int y) {
    	sum += map[x][y];
    	v.push_back({ x, y });
    	check[x][y] = true;
    	for (int dir = 0; dir < 4; ++dir) {
    		int d_x = x + dx[dir];
    		int d_y = y + dy[dir];
    		if (isBound(d_x, d_y) && !check[d_x][d_y]) {
    			if (abs(map[x][y] - map[d_x][d_y]) >= L && abs(map[x][y] - map[d_x][d_y]) <= R) {
    				dfs(d_x, d_y);
    			}
    		}
    	}
    }
    bool task() {
    	bool change = false;
    	memset(check, 0, sizeof(check));
    	for (int i = 0; i < N; ++i) {
    		for (int j = 0; j < N; ++j) {
    			if (check[i][j]) continue;
    			sum = 0;
    			v.clear();
    			dfs(i, j);
    			if (v.size() == 1) continue;
    			for (auto e : v) {
    				map[e.first][e.second] = sum / v.size();
    			}
    			change = true;
    		}
    	}
    	return change;
    }
    int main() {
    	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]);
    		}
    	}
    	while (task()) { ans++; }
    	printf("%d\n", ans);
    	return 0;
    }
Algorithm