BOJ_16234 / C++

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

16234번: 인구 이동

백준 온라인저지 16234번 문제입니다. 

BFS을 이용해서 풀었습니다.

#include<iostream>
#include <queue>
#include<stack>
#include<cstring>
using namespace std;

int arr[101][101];
bool visited[101][101];
int N, L, R;

int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };

stack<pair<int, int>> stk;
queue<pair<int, int>> graph;

// 입력을 받는 역활
void Input() {
	cin >> N >> L >> R;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> arr[i][j];
		}
	}
}

//국경선 open시 인원 배분하는 역활
bool ChangeArray(int result) {

	//국경선 열리지 않음
	if (result == -1 ) return false;

	while (!stk.empty()) {
		int y = stk.top().first;
		int x = stk.top().second;
		stk.pop();
		arr[y][x] = result;
	}
	return true;
}

//인원 배분이 필요한 나라를 찾는 역활
int bfs(int a, int b) {
	graph.push({ a, b });

	int country_cnt = 0;
	int members = 0;

	while (!graph.empty()) {
		int y = graph.front().first;
		int x = graph.front().second;
		graph.pop();

		//방문처리
		if (visited[y][x]) continue;
		visited[y][x] = true;
		
		stk.push({ y,x });
		country_cnt++;
		members += arr[y][x];

		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny >= N || ny < 0 || nx >= N || nx < 0) continue;
			if (abs(arr[y][x] - arr[ny][nx]) >= L && abs(arr[y][x] - arr[ny][nx]) <= R) {
				if (visited[ny][nx]) continue;
				graph.push({ ny,nx });
					
			}
				
		}
	}

	// 국경선을 open하는 나라가 없을때
	if (country_cnt <= 1) {
		if(!stk.empty()) stk.pop();
		return -1;
	}

	//국경선 open시 공유할 나라의 인원 배분 값
	return members / country_cnt;
}

//함수 조합 역활
int solution() {
	int move_cnt = 0;
	bool flag;
	do{
		flag = false;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				// 한번이라도 국경선을 열었을때 flag on
				if (ChangeArray(bfs(i, j)))
					flag = true;
			}
		}
		if(flag)
			move_cnt++;
		memset(visited, false, sizeof(visited));
	} while (flag);

	return move_cnt;
}

int main(void) {
	
	Input();
	int sol = solution();
	cout << sol;
}

아이디어

1. 모든 나라를 방문하며 국경선이 열리는 조건 확인

2. 국경선을 open시 해당 지역 인원 분배

3. 국경선을 한번이라도 open시 카운팅과 다시한번더 루틴을 돌 수 있게 flag 변화

 

국경선을 open 조건을 만족하는 나라들을 잘처리하는게 핵심으로 생각됨

본인은 그래프를 한번에 돌지 않고 조건에 맞는 나라들만 stack에 담고 바로바로 처리했음