백준 문제풀이/GOLD
[백준 / BOJ / GOLD 5] 16234 번 : 인구 이동
지나가던 개발자
2021. 3. 22. 23:49
반응형
16234번: 인구 이동
N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모
www.acmicpc.net
문제 접근법
- 땅의 크기와 이동 횟수가 몇번인지 생각해본다
- 땅의 크기 최대 50 * 50 = 2500
- 이동은 최대 2000번까지
- 단순 순회 가정이 5,000,000
- DFS를 사용하여 땅을 순회하며 연합이 가능한지 체크한다.
- 연합을 한 땅끼리 값을 더 해준뒤 땅 갯수만큼 나누어서 분배한다.
- 이를 더 이상 연합이 생기지 않을 때 까지 반복한다.
아래는 코드입니다.
|
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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
|
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };
int N, L, R, aCount = 0, ans = 0, sum = 0;
int board[50][50];
bool check[50][50];
bool endCheck;
queue<pair<int, int>> q;
bool InRange(int x, int y)
{
return x >= 0 && x < N && y >= 0 && y < N;
}
bool InRange2(int x, int y)
{
if (x > y)
{
int n = x - y;
return n >= L && n <= R;
}
else
{
int n = y - x;
return n >= L && n <= R;
}
}
void DFS(int x, int y)
{
aCount++;
sum += board[x][y];
q.push(make_pair(x, y));
for (int i = 0; i < 4; i++)
{
int nx = x + dx[i];
int ny = y + dy[i];
if (InRange(nx, ny) && !check[nx][ny] && InRange2(board[x][y], board[nx][ny]))
{
check[nx][ny] = true;
DFS(nx, ny);
}
}
}
void BoardChange(int x, int y)
{
if (aCount == 1)
{
sum = 0;
aCount = 0;
while (!q.empty())
q.pop();
return;
}
sum /= aCount;
while (!q.empty())
{
int x = q.front().first;
int y = q.front().second;
q.pop();
board[x][y] = sum;
}
sum = 0;
aCount = 0;
endCheck = false;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> N >> L >> R;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
cin >> board[i][j];
endCheck = false;
while (!endCheck)
{
endCheck = true;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (!check[i][j])
{
check[i][j] = true;
DFS(i, j);
BoardChange(i, j);
}
}
}
memset(check, false, sizeof(check));
if (!endCheck)
ans++;
}
cout << ans << "\n";
return 0;
}
|
cs |
반응형