728x90
문제
16234번: 인구 이동
N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모
www.acmicpc.net
문제 해결
1. BFS를 이용해서 탐색을 할 때 방문할 노드가 개방 가능 조건에 있다면 border배열을 true로 해준다
2. true로 되어 있는 노드를 하나 방문 후 연결되어 있는 모든 true노드를 방문한다.
3. 방문할 때마다 cnt++ 을 해줘서 몇 개의 노드를 방문해 줬는지와 sum+=map [y][x]를 해줌으로써 방문한 노드들의 평균값을 구할 수 있다.
4. 방문을 마친 노드에 대해서는 다시 방문하면 안 됨므로 border배열에서 false를 해준다.
5. 노드들의 평균값을 가지고 방문한 노드의 값을 바꿔준다.
6. 위 방법을 방문할 노드가 없을 때까지 반복한다
|
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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
|
#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
#define max 55
using namespace std;
int N,L,R,result = 0;
int map[max][max];
bool border[max][max] = {false};
bool visit[max][max] = {false};
vector <pair<int,int>> node;
bool ck(int y,int x){
if(y<0||x<0||x>=N||y>=N){return false;}
else{return true;}
}
void change(int num){
for(int i = 0;i<node.size();i++){
int y = node[i].first;
int x = node[i].second;
map[y][x] = num;
}
}
void set(int y,int x){
queue<int> dx;
queue<int> dy;
dy.push(y);
dx.push(x);
while(1)
{
if(dy.empty() == 1){break;}
x = dx.front();
y = dy.front();
dx.pop();
dy.pop();
if(visit[y][x] == true){continue;}
else{visit[y][x] = true;}
//상
if(ck(y-1,x)){
dy.push(y-1);dx.push(x);
int temp = map[y][x]-map[y-1][x];
if(temp < 0){temp = temp*-1;}
if(temp>=L&&temp<=R){border[y][x] = true;
border[y-1][x] = true;}
}
//하
if(ck(y+1,x)){
dy.push(y+1);dx.push(x);
int temp = map[y][x]-map[y+1][x];
if(temp < 0){temp = temp*-1;}
if(temp>=L&&temp<=R){border[y][x] = true;
border[y+1][x] = true;}
}
//좌
if(ck(y,x-1)){
dy.push(y);dx.push(x-1);
int temp = map[y][x]-map[y][x-1];
if(temp < 0){temp = temp*-1;}
if(temp>=L&&temp<=R){border[y][x] = true;
border[y][x-1] = true;}
}
//우
if(ck(y,x+1)){
dy.push(y);dx.push(x+1);
int temp = map[y][x]-map[y][x+1];
if(temp < 0){temp = temp*-1;}
if(temp>=L&&temp<=R){border[y][x] = true;
border[y][x+1] = true;}
}
}
}
int BFS(int y,int x){
int temp = 0,cnt = 0,sum = 0;
queue<int> dx;
queue<int> dy;
dx.push(x);
dy.push(y);
while(1){
if(dy.empty()==1){break;}
x = dx.front();dx.pop();
y = dy.front();dy.pop();
if(visit[y][x]){continue;}
else{
//cout << map[y][x] << " ";
visit[y][x] = true;
node.push_back(make_pair(y,x));
border[y][x] = false;
sum += map[y][x];
cnt++;
}
if(ck(y-1,x)){
temp = map[y][x]-map[y-1][x];if(temp<0){temp = temp*-1;}
if(temp>=L&&temp<=R){
dy.push(y-1);
dx.push(x);
}
}
if(ck(y+1,x)){
temp = map[y][x]-map[y+1][x];if(temp<0){temp = temp*-1;}
if(temp>=L&&temp<=R){
dy.push(y+1);
dx.push(x);
}
}
if(ck(y,x-1)){
temp = map[y][x]-map[y][x-1];if(temp<0){temp = temp*-1;}
if(temp>=L&&temp<=R){
dy.push(y);
dx.push(x-1);
}
}
if(ck(y,x+1)){
temp = map[y][x]-map[y][x+1];if(temp<0){temp = temp*-1;}
if(temp>=L&&temp<=R){
dy.push(y);
dx.push(x+1);
}
}
}
return (sum/cnt);
}
int solve(void){
int stop = 0;
for(int i = 0;i<N;i++){
for(int j = 0;j<N;j++){
if(border[i][j]){
stop++;
int num = BFS(i,j);
change(num);
node.clear();
}
}
}
if(stop>0){result++;}
return stop;
}
int main(void){
cin >> N >> L >> R;
for(int i = 0;i<N;i++){
for(int j = 0;j<N;j++){cin >> map[i][j];}
}
while(1){
memset(visit,false,sizeof(visit));
memset(border,false,sizeof(border));
set(0,0);
memset(visit,false,sizeof(visit));
int stop = solve();
if(stop == 0){break;}
}
cout << result;
}
|
cs |
728x90
'그래프 이론 > BFS, DFS 알고리즘' 카테고리의 다른 글
| [백준/C++][나이트의 이동(7562번)] (0) | 2020.12.02 |
|---|---|
| [백준/C++][연결 요소의 개수(11724번)] (0) | 2020.12.01 |
| [백준/C++][(1167번)트리의 지름] (0) | 2020.11.21 |
| [백준/C++] 치즈(2638번) (0) | 2020.11.11 |
| [백준/C++]연구소(14502) (0) | 2020.11.07 |