복잡한 2차원 영역을 1차원으로 변환한 후 bfs 알고리즘을 이용하여 문제 해결하였습니다.
위 사진 처럼 각 국경선이 열린 경우 점선으로 표시가 되는데 이를 나타내기 위해서2차원 영역을 1차원으로 변환하는 게 좋다.(구현이 가능하지만 복잡해지기 때문에)
각 2차원 좌표에 차례대로 번호를 붙여 1차원 좌표로 변환한다. 2차원 좌표를 1차원 좌표로 변환하는 코드는 다음과 같다.
int xy2number(int y, int x) {
//2차원 좌표 -> 1차원 좌표로 변환
return y * N + x;
}
0
1
2
3
위의 2차원 좌표를 변환하면 다음과 같다.
0
1
2
3
그 후 국경선을 열었는 지 확인하는 벡터를 생성한다.
isOpen = vector<vector<bool>>(N * N, vector<bool>(N * N, false));
예를들어 isOpen() 의 값은 0번 국가가 1번 국가에 대하여 국경선을 연 경우true, 닫은 경우false값을 가진다.
위의 변환 코드를 이용하여 모든 국가에 대하여 isOpen을 기록하는 함수를 실행한다. 아무 국가도 국경선을 열지 않는 경우false를 반환하여 알고리즘을 종료한다.
// 각 국가에 대하여 인구수 차이를 계산하고, 국경선을 열었는 지에 대한 벡터 생성
bool find_diff_and_open() {
bool open = false; // 국경선을 하나도 열지 않은 경우 false 반환, 국경선을 연 경우 true 반환
isOpen = vector<vector<bool>>(N * N, vector<bool>(N * N, false));
// 국경선을 열었는지에 대한 벡터 ex) isOpen[1][2] -> 1번 국가는 2번 국가에 대해 Open
for (int y = 0; y < N; ++y) {
for (int x = 0; x < N; ++x) {
//board[y][x]에 대하여 인접 국가 탐색
for (int d = 0; d < 4; ++d) {
int ny = y + dy[d];
int nx = x + dx[d];
if (ny < 0 || nx < 0 || ny >= N || nx >= N)
continue;
int diff = abs(board[ny][nx] - board[y][x]); // 인구 수 차이
if (diff >= L && diff <= R) {
open = true;
// 2차원 좌표 -> 1차원 좌표로 변환
int num1 = xy2number(y, x);
int num2 = xy2number(ny, nx);
// 국경선 Open 기록
isOpen[num1][num2] = isOpen[num2][num1] = true;
}
}
}
}
return open;
}
start()함수는find_diff_and_open()함수가true를 반환하는 동안 bfs 탐색을 하여 인구수를 갱신하고 count를 셈하도록 되어있다.
int start() {
int count = 0; //국경선을 개방한 경우 반복, 개방한 국경선이 없는 경우 count 반환
while(find_diff_and_open()){
count++;
// 국경선을 개방한 경우 bfs 알고리즘을 이용하여 영역 탐색 및 인구 수 갱신
bfs();
}
return count;
}
bfs()함수에서 국경선을 개방한 연합국가를 탐색하여 인구수를 갱신해준다.
// 모든 좌표에 대하여 bfs 탐색
void bfs(){
used = vector<vector<bool>>(N, vector<bool>(N, false));
for(int y = 0; y < N; ++y){
for (int x = 0; x < N; ++x){
if(!used[y][x]) // 사용하지 않은 좌표에 대하여 bfs()
_bfs(y, x);
}
}
}
void _bfs(int start_y, int start_x){ //bfs를 이용한 영역 탐색
queue<pair<int ,int>> q;
vector<pair<int, int>> union_vector; // 같은 연합의 좌표를 저장하는 벡터
q.push(make_pair(start_y, start_x));
union_vector.push_back(make_pair(start_y, start_x));
while(!q.empty()){
int y = q.front().first;
int x = q.front().second;
q.pop();
used[y][x] = true; //인접 좌표 탐색
for(int d = 0; d < 4; ++d){
int ny = y + dy[d];
int nx = x + dx[d];
if (ny < 0 || nx < 0 || ny >= N || nx >= N || used[ny][nx])
continue;
int num1 = xy2number(y, x);
int num2 = xy2number(ny, nx);
// 국경선이 열린 좌표인 경우
if(isOpen[num1][num2]){
used[ny][nx] = true;
union_vector.push_back(make_pair(ny,nx)); // 연합 벡터에 추가
q.push(make_pair(ny, nx));
}
}
}
if(union_vector.size() == 1) return; // 연합이 1개인 경우 리턴
// 연합의 인구수 합 계산 및 인구 수 갱신
int sum = 0;
//같은 연합의 합 검색
for (int i = 0 ; i < union_vector.size(); ++i){
int y = union_vector[i].first;
int x = union_vector[i].second;
sum += board[y][x];
}
int new_num = (int)(sum/union_vector.size()); // 연합의 새로운 인구 수
// 연합의 인구 수 갱신
for (int i = 0 ; i < union_vector.size(); ++i){
int y = union_vector[i].first;
int x = union_vector[i].second;
board[y][x] = new_num;
}
}
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <numeric>
using namespace std;
int N, L, R;
vector<vector<int>> board;
vector<vector<bool>> isOpen;
vector<vector<bool>> used;
int dy[4] = {0, 1, 0, -1};
int dx[4] = {-1, 0, 1, 0};
int xy2number(int y, int x) {
return y * N + x;
}
bool find_diff_and_open() {
bool open = false;
isOpen = vector<vector<bool>>(N * N, vector<bool>(N * N, false));
for (int y = 0; y < N; ++y) {
for (int x = 0; x < N; ++x) {
for (int d = 0; d < 4; ++d) {
int ny = y + dy[d];
int nx = x + dx[d];
if (ny < 0 || nx < 0 || ny >= N || nx >= N)
continue;
int diff = abs(board[ny][nx] - board[y][x]);
if (diff >= L && diff <= R) {
open = true;
int num1 = xy2number(y, x);
int num2 = xy2number(ny, nx);
isOpen[num1][num2] = isOpen[num2][num1] = true;
}
}
}
}
return open;
}
void _bfs(int start_y, int start_x){
queue<pair<int ,int>> q;
vector<pair<int, int>> union_vector;
q.push(make_pair(start_y, start_x));
union_vector.push_back(make_pair(start_y, start_x));
while(!q.empty()){
int y = q.front().first;
int x = q.front().second;
q.pop();
used[y][x] = true;
for(int d = 0; d < 4; ++d){
int ny = y + dy[d];
int nx = x + dx[d];
if (ny < 0 || nx < 0 || ny >= N || nx >= N || used[ny][nx])
continue;
int num1 = xy2number(y, x);
int num2 = xy2number(ny, nx);
if(isOpen[num1][num2]){
used[ny][nx] = true;
union_vector.push_back(make_pair(ny,nx));
q.push(make_pair(ny, nx));
}
}
}
// sum of union
if(union_vector.size() == 1) return;
int sum = 0;
for (int i = 0 ; i < union_vector.size(); ++i){
int y = union_vector[i].first;
int x = union_vector[i].second;
sum += board[y][x];
}
int new_num = (int)(sum/union_vector.size());
for (int i = 0 ; i < union_vector.size(); ++i){
int y = union_vector[i].first;
int x = union_vector[i].second;
board[y][x] = new_num;
}
}
void bfs(){
used = vector<vector<bool>>(N, vector<bool>(N, false));
for(int y = 0; y < N; ++y){
for (int x = 0; x < N; ++x){
if(!used[y][x])
_bfs(y, x);
}
}
}
int start() {
int count = 0;
while(find_diff_and_open()){
count++;
bfs();
}
return count;
}
int main() {
// initialize
cin >> N >> L >> R;
board = vector<vector<int>>(N, vector<int>(N, 0));
isOpen = vector<vector<bool>>(N * N, vector<bool>(N * N, false));
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
cin >> board[i][j];
}
}
//start
cout << start();
}
