728x90
인구 이동
문제
N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다.
오늘부터 인구 이동이 시작되는 날이다.
인구 이동은 하루 동안 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다.
- 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루 동안 연다.
- 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다.
- 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다.
- 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 편의상 소수점은 버린다.
- 연합을 해체하고, 모든 국경선을 닫는다.
각 나라의 인구수가 주어졌을 때, 인구 이동이 며칠 동안 발생하는지 구하는 프로그램을 작성하시오.
설명
연결된 모든 인덱스를 방문하여 평균을 구해주는 문제.
처음 풀때 여기서 연결된? 이 부분을 이중 반복문을 이용해
map[i][j], map[i][j+1] 의 값 비교와
map[i][j], map[i+1][j] 의 값 비교를 하여 구하였는데 너무 복잡해져서
bfs를 이용하여 해결하였다. 방문하지 않았으면 방문하여 조건에 충족하는 모든 인덱스를 vector에 저장하여
move() 함수에서 해당 인덱스에 접근하여 계산해준다.
끝!
소스코드
|
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
|
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
#define MAX 50
using namespace std;
int n, l, r;
struct pos {
int y, x;
};
int map[MAX][MAX];
bool visited[MAX][MAX];
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };
vector<pos> v;
int ans, sum, cnt;
bool flag;
void move()
{
int avg = sum / cnt;
for (int i = 0; i < cnt; i++)
{
map[v[i].y][v[i].x] = avg;
}
}
void bfs(int y, int x)
{
queue<pos> q;
q.push({ y,x });
visited[y][x] = true;
v.push_back({y,x});
sum += map[y][x];
cnt++;
while (!q.empty())
{
int y = q.front().y;
int x = q.front().x;
q.pop();
for (int i = 0; i < 4; i++)
{
int ny = y + dy[i], nx = x + dx[i];
if (ny >= 0 && nx >= 0 && ny < n && nx < n)
{
if (!visited[ny][nx])
{
int temp = abs(map[y][x] - map[ny][nx]);
if (temp >= l && temp <= r)
{
q.push({ ny,nx });
visited[ny][nx] = true;
v.push_back({ ny,nx });
sum += map[ny][nx];
cnt++;
}
}
}
}
}
if (v.size() > 1)
{
move();
flag = true;
}
sum =0, cnt =0;
v.clear();
}
int main()
{
cin >> n >> l >> r;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cin >> map[i][j];
}
}
while (true)
{
memset(visited, false, sizeof(visited));
flag = false;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (!visited[i][j])
{
bfs(i, j);
}
}
}
if (flag)ans++;
else break;
}
cout << ans;
return 0;
}
|
cs |
LIST
'Programming > Algorithm' 카테고리의 다른 글
| [Level2 프로그래머스] 오픈채팅방 c++ (0) | 2021.09.24 |
|---|---|
| [Level2 프로그래머스] 문자열 압축 (0) | 2021.09.24 |
| [구현 BOJ-15685] 드래곤 커브, c++ (1) | 2021.08.09 |
| [구현, BOJ-15684] 사다리 조작, c++ (1) | 2021.08.09 |
| [시뮬레이션, BOJ-15683]감시, c++ (0) | 2021.06.04 |