문제:
- 제목: 인구이동
- 링크 : https://www.acmicpc.net/problem/16234
해결 방식:
BFS (+로직)
- 얻어간점
- 종료조건을 정확히 주자
- 종료조건 중, 언제 끝나는지에 대한 논리를 정확히하자
- 종료조건을 통해서 출력되는게 무엇인가에 대한 논리 또한 정확히 하자
CODE
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <string.h>
#include <queue>
#include <algorithm>
using namespace std;
int graph[51][51] = { 0, };
int visited[51][51] = { 0, };
int moved = 0;
int moved_time = 0;
int dr[4] = { -1,1,0,0 };
int dc[4] = { 0,0,-1,1 };
int N, L, R;
int check = 0;
void people_move() {
memset(visited, 0, sizeof(visited));
queue<pair<int,int>> q;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (visited[i][j] == 0) {
vector<pair<int, pair<int,int>>> temp;
temp.push_back({ graph[i][j], {i,j} });
visited[i][j] = 1;
q.push({ i,j });
while (!q.empty()) {
pair<int, int> cur_step = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
pair<int, int> next_step = { cur_step.first + dr[i], cur_step.second + dc[i] };
if (next_step.first < 0 || next_step.first >= N || next_step.second < 0 || next_step.second >= N) {
continue;
}
if (visited[next_step.first][next_step.second] != 0) {
continue;
}
if (abs(graph[cur_step.first][cur_step.second] - graph[next_step.first][next_step.second]) < L) {
continue;
}
if (abs(graph[cur_step.first][cur_step.second] - graph[next_step.first][next_step.second]) > R) {
continue;
}
visited[next_step.first][next_step.second] = 1;
temp.push_back({ graph[next_step.first][next_step.second], next_step });
q.push(next_step);
}
}
int avg = 0;
for (int i = 0; i < temp.size(); i++) {
avg = avg + temp[i].first;
}
avg = avg / (temp.size());
//update
for (int i = 0; i < temp.size(); i++) {
if (graph[temp[i].second.first][temp[i].second.second] != avg) {
check = 1;
}
graph[temp[i].second.first][temp[i].second.second] = avg;
}
}
}
}
// 종료조건의 논리를 정확히하자. 언제 끝나는가? : 맵의 업데이트가 없을때
// 무엇을 출력해야하는가? : 맵의 업데이트가 있다면 있었던 날짜증가
if (check == 0) {
cout << moved_time;
exit(0);
}
else {
moved_time = moved_time + 1;
}
}
int main() {
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
freopen("텍스트.txt", "r", stdin);
cin >> N >> L >> R;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> graph[i][j];
}
}
while (1) {
people_move();
check = 0;
}
cout << moved;
exit(0);
}