[백준(BOJ)] 16234번 : 인구 이동 - C++[CPP]

https://www.acmicpc.net/problem/16234

16234번: 인구 이동

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 구현
• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 시뮬레이션

 

---

 

⊙ 문제 접근 과정

 

너비 우선 탐색(bfs)을 이용해 풀었다.

거기에 for문을 한번 더 감쌌다. L과 R의 범위로 인해 연합국이 생기지 않을 때까지 이 for문을 반복한다.

한 바퀴 돌 때마다 days가 1 증가

 

연합국이 생기지 않는다면 days(결과)를 출력한다.

 

자세한 풀이는 코드 참고!

---

 

⊙ 문제 풀이

 

#include<iostream>
#include<queue>

using namespace std;
#define MAX 51

int N, L, R, arr[MAX][MAX];
bool visited[MAX][MAX];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

queue<pair<int, int>> q;
vector<pair<int, int>> v;

bool flag = true; //연합여부
int sum = 0; //평균을 구하기 위한 변수

void bfs(pair<int, int> start) { //bfs
	q.push(start);
	visited[start.first][start.second] = true;

	while (!q.empty()) {
		pair<int, int> temp = q.front();
		q.pop();
		
		for (int i = 0; i < 4; i++) {
			int na = temp.first + dx[i];
			int nb = temp.second + dy[i];

            //범위 안에 있고 인구 차이가 L 이상, R 이하 여부 체킹
			if (na >= 0 && nb >= 0 && na < N && nb < N && !visited[na][nb]) {
                if (abs(arr[na][nb] - arr[temp.first][temp.second]) >= L &&
				    abs(arr[na][nb] - arr[temp.first][temp.second]) <= R) {
				        q.push({ na, nb });
				        visited[na][nb] = true;

				        v.push_back({ na, nb });
				        sum += arr[na][nb]; //평균을 구하기 위해
			    }
            }
		}
	}
}

void clear() { //방문 초기화
	for (int i = 0; i < N; i++) 
		for (int j = 0; j < N; j++) 
			visited[i][j] = false;
}

int main() {
    int days = 0; //결과 초기화

	cin >> N >> L >> R;

	for (int i = 0; i < N; i++) //값 입력받기
		for (int j = 0; j < N; j++)
			cin >> arr[i][j];

	while (flag) { //연합이 일어나면 계속 반복
		flag = false; //연합 여부 초기화
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (!visited[i][j]) { //방문을 안 했다면
					v.clear();
					v.push_back({ i,j }); 
					sum = arr[i][j];
					bfs({ i, j });
				}

                //연합 여부
				if (v.size() >= 2) {
					flag = true; //연합 체크
					for (int i = 0; i < v.size(); i++) {
						arr[v[i].first][v[i].second] = sum / v.size(); //평균 갱신
					}
				}
			}
		}
		if (flag) days++; //한바퀴

		clear(); //초기화
	}
	cout << days; //결과
}

---

⊙ 결과

 

---

⊙ 마무리

 

 

NONE

 

좋아요는 로그인하지 않아도 누를 수 있습니다!