[백준 16234] - 인구 이동(bfs) C++

문제

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

16234번: 인구 이동

접근방법

bfs를 이용해 푸는 문제였다.

 

처음 dfs로 접근했는데, dfs로 풀기엔 쉽지 않을 거 같다.

sum과 cnt를 계산해야하는데 dfs를 사용하면 복잡해진다.

 

어쨋든 dfs든 bfs든 포인트는 돌면서 마주친 나라들을 배열에 담아두어서

나중에 한번에 sum과 cnt를 계산해 table의 값을 변경해 주는 것이다.

이를 위해서 table을 전역변수로 설정하는 것이 유리하다.

 

문제를 풀면서 내가 착각했던 부분은 탐색하는 방향이다.

어차피 왼쪽에서 오른쪽, 위에서 아래로 탐색하므로 bfs에서 검사해야할 방향도 아직 탐색하지 않은 우측, 아래일 것이라고 생각했다.

 

하지만, 왼쪽과 위쪽 모두 검사해야했다. 

왜냐하면, 한 번 bfs가 돌고나면 연합이 된 나라들은 값이 변한다. 그러면 연합을 할 수 있었지만 못하는 나라가 생겨버릴 수 있다.

예를 들어, 위에서 한칸 아래 나라와 연합을 한다.

한 칸아래로 내려와서 우측과 아래만 검사하게 되면, 왼쪽나라와 연합을 할 수 있는 기회가 있어도 하지 못한다.

이렇게 연합이 끝나고 table의 값이 변경되면, 왼쪽 나라에 도착했을 때 이미 오른쪽 나라의 값은 변경되어 연합을 하지 못한다.

 

우리는 한 번의 시도마다 연합할 수 있는 모든 나라들을 연합해야하기 때문에, 이런 식으로 풀면 안된다. 모든 방향을 탐색해야 하는 것이다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
#include <cmath>

using namespace std;

#define FOR(i, n) for(int i=0;i<n;i++) 
#define FASTERIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define MAX 987654321


vector<vector<int>> ddang;
vector<vector<bool>> visited;
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
int N, L, R;
bool checkToGo(int y, int x) {
    return (y >= 0 && y < N && x >= 0 && x < N) && !visited[y][x];
}

bool checkToUnion(int ny, int nx, int y, int x) {
    return abs(ddang[ny][nx] - ddang[y][x]) >= L && abs(ddang[ny][nx] - ddang[y][x]) <= R;
}

bool bfs(int y, int x) {
    queue<pair<int, int>> mq;
    queue<pair<int, int>> bowl;
    int cnt = 0;
    int sum = 0;
    bool is_union = false;
    mq.push({y, x});
    bowl.push({y, x});
    visited[y][x] = true;
    while(!mq.empty()) {
        const auto& [y, x] = mq.front();
        mq.pop();
        cnt++;
        sum += ddang[y][x];
        FOR(i, 4) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (checkToGo(ny, nx)) {
                if (checkToUnion(ny, nx, y, x)) {
                    visited[ny][nx] = true;
                    mq.push({ny, nx});
                    bowl.push({ny, nx});
                }
            }
        }
    }
    if (bowl.size() > 1) is_union = true;
    while(!bowl.empty()) {
        const auto& [y, x] = bowl.front();
        bowl.pop();
        ddang[y][x] = sum / cnt;
    }
    return is_union;
}

//연합 했는 지 안했는 지 여부를 반환
bool isUnion() {
    bool is_union = false;
    visited = vector<vector<bool>>(N, vector<bool>(N, false));
    FOR(i, N) FOR(j, N) 
        if (!visited[i][j]) {
            if (bfs(i, j)) is_union = true;
        }
    return is_union;
}

int main() {
    cin >> N >> L >> R;
    ddang = vector<vector<int>>(N, vector<int>(N));
    FOR(i, N) FOR(j, N) cin >> ddang[i][j];
    int ret = 0;
    while(isUnion()) ret++;
    cout << ret << endl;
    return 0;
}

 

개선할 점

복잡한 문제였다. 이런 문제를 풀 수 있으려면, 함수를 잘 만들어야한다.

 

이번엔 checkToGo와 checkToUnion 함수 코드를 잘 못짜서 헤멨다.

&&와 ||을 헷갈리는 바람에 자꾸 segmentation error가 떴다.