백준 16234번: 인구 이동 (C++)

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

16234번: 인구 이동

접근

이번에 C++ 언어를 새로 익히면서, 언어에 익숙해지기 위해 백준 문제들을 C++ 언어로 풀어보기로 했다. 익숙한 파이썬으로 풀었던 문제들을 몇 문제 동일한 알고리즘으로 C++로 풀어본 다음 새로운 문제도 C++로 풀어보는 순서로 접근하기로 했다. 그 첫번째로 비교적 간단한 문제인 이 문제를 C++로 풀어보았다.

각 위치의 인구수를 저장해주는 matrix 매트릭스, 방문 여부를 저장해주는 visited 매트릭스를 사용하고, bfs 알고리즘을 이용하여 문제를 해결하였다.

1. 모든 칸을 탐색하면서, 방문하지 않았던 칸을 만나면 해당 칸을 기점으로 bfs 알고리즘을 이용하여 탐색하기 시작한다.
2. bfs 함수에서는 기본 칸을 기점으로 상하좌우 새로운 칸에 국경을 열게 되는지 확인하여 열게되면 해당 칸을 큐에 추가하여 국경을 열게되는 모든 칸을 탐색하여 국경을 여는 모든 칸의 인구수의 합, 국경을 열게되는 국가의 수를 저장한다. 계산된 평균 인구수를 국경을 연 모든 국가에 저장해준다.
3. 국경을 여는 기준에 부합하는 국가가 없을 경우 인구 이동을 중단한다.

참고 파이썬 코드:

2022.03.05 - [코딩/백준 (Python)] - 백준 16234번: 인구 이동 (Python, PyPy3)

백준 16234번: 인구 이동 (Python, PyPy3)

코드

#include<iostream>
#include<queue>

#define MAX_N 50

using namespace std;

int N, L, R;
int matrix[MAX_N][MAX_N];
int visited[MAX_N][MAX_N];
int ansDay = 0;

int dr[] = { 0, 1, 0, -1 };
int dc[] = { 1, 0, -1, 0 };
bool flag = true;

void bfs(int r, int c)
{
    queue<pair<int, int>> Q, Q2;
    Q.push(make_pair(r, c));
    Q2.push(make_pair(r, c));
    visited[r][c] = 1;
    int sum = 0;
    int cnt = 0;

    while (Q.empty() == 0)
    {
        int now_r = Q.front().first;
        int now_c = Q.front().second;
        Q.pop();

        sum = sum + matrix[now_r][now_c];
        cnt++;
        for (int i = 0; i < 4; i++)
        {
            int nr = now_r + dr[i];
            int nc = now_c + dc[i];

            if (nr < 0 || N <= nr || nc < 0 || N <= nc) continue;
            if (visited[nr][nc] == 1) continue;
            if ((L <= abs(matrix[now_r][now_c] - matrix[nr][nc])) && (abs(matrix[now_r][now_c] - matrix[nr][nc]) <= R))
            {
                visited[nr][nc] = 1;
                Q.push(make_pair(nr, nc));
                Q2.push(make_pair(nr, nc));
            }
        }
    }
    int val = sum / cnt;

    while (Q2.empty() == 0)
    {
        int x = Q2.front().first;
        int y = Q2.front().second;
        Q2.pop();
        matrix[x][y] = val;
    }
}

bool can_move(int r, int c)
{
    for (int i = 0; i < 4; i++)
    {
        int nr = r + dr[i];
        int nc = c + dc[i];

        if (nr < 0 || N <= nr || nc < 0 || N <= nc) continue;
        if ((L <= abs(matrix[r][c] - matrix[nr][nc])) && (abs(matrix[r][c] - matrix[nr][nc]) <= R))
        {
            return true;
        }
    }
    return false;
}


int main(int argc, char** argv)
{    
    // freopen("input.txt", "r", stdin);

    scanf("%d %d %d", &N, &L, &R);

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            scanf("%d", &matrix[i][j]);
        }
    }

    while (flag)
    {
        flag = false;
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                if (!visited[i][j] and can_move(i, j))
                {
                    bfs(i, j);
                    flag = true;
                }
            }
        }
        if (flag == true)
        {
            ansDay++;
        }
        memset(visited, 0, sizeof(visited));
    }

    printf("%d\n", ansDay);
    return 0;
}

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!