[C++] 백준 16234 인구 이동 - 구현과 그래프 탐색의 응용문제, 반복문 설계

문제

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

리뷰

문제 유형: 구현, 시뮬레이션, 그래프 탐색, 자료구조

 

그래프 탐색의 약간의 변형문제이다.

그래프 탐색을 진행할 때는 보통 DFS의 재귀, BFS의 큐 방식을 이용하고, 재귀 혹은 큐를 위한 '조건'을 설계한다.

문제에 따라서 해당 조건은 예를 들어, 해당 지점보다 작은 값으로 or 방문하지 않았던 곳으로 or 해당위치와 같은 값을 갖는 곳으로 ... 등등등의 조건이 생성된다.

해당 문제도 동일하다만, '조건'을 설계하고 plus, 전체적인 반복 시퀀스를 구성해야 한다는 점이 다른 점이다.

'전체 x, y 좌표'를 x++, y++ 해 가면서 그래프 탐색을 응용해 문제를 해결해나가야 함을 파악하기 어려웠다.

유형이 동일함을 파악한다면 어렵지 않은 문제였다.

 

주의할 점

전체 반복문 안에서 answer ++ 하는 타이밍을 잘 생각해야 하고, 전체 반복문을 언제 break 해야 하는지에도 주의해야 한다.

 

코드

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <cmath>

using namespace std;

int N, L, R;
int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int map[51][51];
bool visited[51][51];

bool InRange(int x, int y){
    return ( x<0 || x>N-1 || y<0 || y>N-1) ? false:true;
}

bool Condition(int v, int x, int y){
    return (abs(map[x][y] - v) > R || (abs(map[x][y] - v) < L)) ? false:true;
}

int Solve(){
    int answer = 0;
    cin >> N >> L >> R;
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++)
            cin >> map[i][j];
    }
    // 인구 이동이 없을 때까지 반복
    while(true){
        bool end_condition = false;
        for(int k=0; k<N; k++)
            memset(visited[k], false, sizeof(bool)*N);

        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                if(visited[i][j])
                    continue;

                // BFS를 통한 조건에 맞는 영역 탐색 
                queue<pair<int, int>> q;
                vector<pair<int, int>> v;
                int sum=map[i][j], cnt=1;  

                visited[i][j] = true;
                q.push({i, j});
                v.push_back({i, j});

                while(!q.empty()){
                    int cx = q.front().first;
                    int cy = q.front().second;
                    int cv = map[cx][cy];
                    q.pop();

                    for(int d=0; d<4; d++){
                        int nx = cx+dir[d][0];
                        int ny = cy+dir[d][1];

                        if(InRange(nx, ny) && !visited[nx][ny] && Condition(cv, nx, ny)){
                            visited[nx][ny] = true;
                            q.push({nx, ny});
                            v.push_back({nx, ny});

                            end_condition = true;                   // 하나라도 있으면 ok
                            sum += map[nx][ny];
                            cnt ++;
                        }
                    }
                }
                //해당 영역 계산
                int value = sum/cnt;
                for(auto iter=v.begin(); iter!=v.end(); iter++){
                    int cx = iter->first;
                    int cy = iter->second;

                    map[cx][cy] = value;
                }
                v.clear();
            }
            /*
            cout << '\n';
            for(int i=0; i<N; i++){
                for(int j=0; j<N; j++)
                    cout << map[i][j] << " ";
                cout << '\n';
            }*/
        }
        if(!end_condition)
            break;

        answer ++;        
    }
    return answer;        
}

int main(){
    int answer = Solve();
    cout << answer;

    return 0;
}

 

비슷한 문제

프로그래머스 프렌즈4블록 https://school.programmers.co.kr/learn/courses/30/lessons/17679#

프로그래머스 컬러링북 https://school.programmers.co.kr/learn/courses/30/lessons/1829

백준 2667 단지번호붙이기 https://www.acmicpc.net/problem/2667