백준 16234 <인구 이동> C++ 풀이

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

16234번: 인구 이동

문제

N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다.

오늘부터 인구 이동이 시작되는 날이다.

인구 이동은 하루 동안 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다.

• 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루 동안 연다.
• 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다.
• 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다.
• 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 편의상 소수점은 버린다.
• 연합을 해체하고, 모든 국경선을 닫는다.

각 나라의 인구수가 주어졌을 때, 인구 이동이 며칠 동안 발생하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N, L, R이 주어진다. (1 ≤ N ≤ 50, 1 ≤ L ≤ R ≤ 100)

둘째 줄부터 N개의 줄에 각 나라의 인구수가 주어진다. r행 c열에 주어지는 정수는 A[r][c]의 값이다. (0 ≤ A[r][c] ≤ 100)

인구 이동이 발생하는 일수가 2,000번 보다 작거나 같은 입력만 주어진다.

출력

인구 이동이 며칠 동안 발생하는지 첫째 줄에 출력한다.

 

 

 

 

#

 

구현이 생각보다 까다로웠던 문제였습니다.

격자 구조의 탐색이다보니 DFS 혹은 BFS를 사용하는 풀이라는 것은 쉽게 파악할 수 있는데, 문제의 조건에 맞게 국경선 별로 그룹화도 해야하고 그룹화가 다 끝나고 나면 전부 값도 변경해줘야하고 그리고 인구 이동이 없을 때 까지 반복할 수 있도록 구현해야 했습니다. 푸는데 시간이 조금 오래 걸리긴 했지만, 차근차근 하나씩 해결하다 보니 해결할 수 있었습니다. 순서대로 하나씩 해결한다고 생각하고 풀면 조금 오래걸리긴 해도 풀어낼 수 있습니다.

 

1. 구조체 선언 -> 연합상태를 확인하고 바로 인구이동된 값을 반영하면, 다른 그룹이 L<  < R을 맞추어 탐색할 때 논리적 오류가 생김. 그렇기 때문에 구조체로 저장해두고 맵 전체의 그룹화 작업이 끝나면 그 때 인구이동 반영값을 갱신

 

2. Init 함수 -> 날마다 인구이동이 끝나고 나면 다시 처음부터 탐색하는 작업을 해야하기 때문에, visited 배열의 값을 하루가 지날때마다 다시 초기화 해주기 위한 함수

 

3. DFS 함수 -> 인접 나라들에 대해 조건에 맞을때, 깊이 우선 탐색을 하도록 구현. 이렇게 구현을 하면 국경선을 열어 같은 연합으로 묶인 나라들의 정보가 DFS의 인자로 받는 v벡터에 담기게됨. 그리고 그 v벡터를 활용한다.

 

4. main 함수 -> 입력값들 받고 map에 저장하고 while문을 돌린다. flag를 만들어줘서 인구 이동이 전혀 없었으면 break 하도록 설계. tv벡터는 그룹화가 다 진행되면 map의 정보를 갱신해야하기 때문에 그 작업을 위한 벡터이고, v벡터는 하나의 그룹화가 진행되는 정보들을 담아두고 인구이동값을 갱신하여 tv에 더해주는 역할.

 

 

#include <string>
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
 
using namespace std;
 
int N, L, R;
 
int map[50][50];
int visited[50][50];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,-1,1 };
 
struct Node
{
    int x;
    int y;
    int val;
    Node(int a, int b, int c)
    {
        x = a;
        y = b;
        val = c;
    }
};
 
void Init()
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            visited[i][j] = 0;
        }
    }
}
 
void DFS(int x,int y,vector<Node>& v)
{
    int curVal = map[x][y];
 
    for (int i = 0; i < 4; i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
 
        if (nx < 0 || nx >= N || ny < 0 || ny >= N || visited[nx][ny] == 1)
            continue;
        if (abs(curVal - map[nx][ny]) < L || abs(curVal - map[nx][ny]) > R)
            continue;
 
        v.push_back({ nx,ny,map[nx][ny] });
        visited[nx][ny] = 1;
        DFS(nx, ny, v);
    }
 
    
}
 
 
int main()
{
    cin >> N >> L >> R;
    int answer = 0;
    
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> map[i][j];
        }
    }
 
    while (true)
    {        
        bool flag = false;
        vector<Node> tv;
        for (int i = 0; i < N; i++)
        {            
            for (int j = 0; j < N; j++)
            {
                vector<Node> v;
 
                if (visited[i][j] == 0)
                {
                    DFS(i, j, v);
                }
 
                if (v.empty() == false)
                {
                    flag = true;
                    int tmp = 0;
                    for (int i = 0; i < v.size(); i++)
                    {
                        Node cur = v[i];
                        tmp += cur.val;
                    }
 
                    tmp = tmp / v.size();
                    for (int i = 0; i < v.size(); i++)
                    {
                        v[i].val = tmp;
                        tv.push_back({ v[i].x,v[i].y,tmp });
                    }
                }
            }
 
            
        }
        for (int i = 0; i < tv.size(); i++)
        {
            Node cur = tv[i];
            map[cur.x][cur.y] = cur.val;
        }
 
        if (flag == false)
            break;
        else
        {
            answer++;
            Init();
        }
    }
    
    cout << answer;
 
}