codingtest

16234번 - 인구 이동

2024-02-20
4분 분량
C++백준

문제 링크

문제 풀이 시간 : 2시간

문제 요약

  • NxN크기의 땅 한칸마다 나라가 존재한다.
  • 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면 두 나라는 연합이 된다.
  • 위의 조건에 해당하는 모든 나라가 연합이 되었다면 그 연합은 인구이동을 한다.
  • 인구 이동은 (연합의 총 인구 수)/(연합을 이루는 나라의 개수) 가 된다.
  • 인구이동이 더이상 이뤄지지 않을 때까지 반복하여 며칠 동안 인구 이동이 발생하는지 구해라

문제 풀이

이 문제는 bfs로 인접한 나라들의 인구를 비교하면서 풀면 간단하게 풀 수 있을 거라고 생각했다.

초기 코드

c++
#include <iostream>
#include <cmath>
#include <queue>
#include <set>

using namespace std;

int n, l, r, ans = 0;
int city[51][51], dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};
bool visited[51][51];
queue<pair<int, int>> q, q2, ali;
set<pair<int, int>> s;

bool check(int x, int y) {
    if (x < 1 || x > n || y < 1 || y > n)
        return false;
    return true;
}

void find(int x, int y) {
    q.push({x, y}); //bfs탐색을 위한 큐
    ali.push({x, y}); //연합 확인을 위한 큐
    int people = city[x][y]; //연합의 인구 수
    visited[x][y] = true;

    while (!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int tx = x + dir[i][0];
            int ty = y + dir[i][1];
            if (check(tx, ty)) { //칸을 넘기지 않고
                if (!visited[tx][ty]) { //방문되지 않았다면
                    int sum = abs(city[x][y] - city[tx][ty]); //인접한 국가의 인구 수 차이
                    if (sum >= l && sum <= r) { //조건에 만족한다면
                        ali.push({tx, ty}); //연합에 추가
                        q.push({tx, ty}); //bfs큐에 추가
                        visited[tx][ty] = true; //방문처리
                        people += city[tx][ty]; //연합 인구수 증가
                    } else {
                        s.insert({tx, ty}); //만족하지 않으면 방문되지 않은 나라를 저장하는 set에 저장
                    }
                }
            }
        }
    }

    people = people / ali.size(); //연합의 각 나라의 인구 수 계산

    while (!ali.empty()) { //각 나라의 인구수 저장
        city[ali.front().first][ali.front().second] = people;
        ali.pop();
    }
    if (!s.empty()) { //연합에 포함되지 않았던 나라들 다시 bfs
        ans++;
        while (true) {
            if (s.empty())
                break;
            x = (*s.begin()).first;
            y = (*s.begin()).second;
            s.erase(s.begin());
            if (!visited[x][y])
                break;
        }
        find(x, y);
    }
}

int main() {
    cin >> n >> l >> r;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> city[i][j];
        }
    }

    int sum = 0;
    while (true) {
        sum++;
        find(1, 1);
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++)
                visited[i][j] = false;
        }
        if (ans == n * n - 1)
            break;
        ans = 0;
    }
    cout << sum - 1;
}

위 코드도 바로 통과를 했다.

근데 아무리 생각해도 저렇게 비효율적으로 할 필요가 있을까?

라는 생각을 하고 다른 사람들은 어떻게 풀었나 한번 찾아봤더니

굳이 s라는 set를 사용하지 않고 방문되지 않은 나라를 탐색하는 방식으로 해도 된다.

나라 개수가 아무리 많아봤자 50x50=2500이므로 시간초과와는 거리가 멀다.

그래서 다시 코드를 수정해서 아래와 같은 결과를 얻을 수 있었다.

최종 코드

c++
#include <iostream>
#include <vector>
#include <queue>

using namespace std;
vector<pair<int, int>> v;
queue<pair<int, int>> q;
int n, l, r, sum = 0;
int city[51][51], dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};
bool visited[51][51];

bool check(int x, int y) {
    if (x < 1 || x > n || y < 1 || y > n)
        return false;
    return true;
}

void find(pair<int, int> input) {
    q.push(input); //bfs탐색을 위한 큐
    visited[input.first][input.second] = true; //방문 처리
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int tx = x + dir[i][0];
            int ty = y + dir[i][1];
            if (!visited[tx][ty]) {
                if (check(tx, ty)) {
                    int temp = abs(city[x][y] - city[tx][ty]);
                    if (temp >= l && temp <= r) {
                        v.push_back({tx, ty}); //연합 처리를 위한 벡터 저장
                        q.push({tx, ty});
                        visited[tx][ty] = true;
                        sum += city[tx][ty]; //인구수 계산
                    }
                }

            }
        }
    }
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> l >> r;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++)
            cin >> city[i][j];
    }
    bool flag = true;
    int ans = 0;
    while (flag) { //연합이 발생하지 않을 때까지 반복
        flag = false;
        for (int i = 1; i <= n; i++) { //모든 나라를 보며 방문되지 않은 경우 bfs실시
            for (int j = 1; j <= n; j++) {
                if (!visited[i][j]) {
                    v.push_back({i, j});
                    sum = city[i][j];
                    find({i, j});
                }
                if (v.size() > 1) { //벡터에 2개이상의 나라가 저장됐다면 연합 발생
                    flag = true;
                    for (int k = 0; k < v.size(); k++) {
                        city[v[k].first][v[k].second] = sum / v.size();
                    }
                }
                v.clear();
            }
        }
        if (flag)
            ans++;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++)
                visited[i][j] = false;
        }

    }
    cout << ans;
}

함께 읽으면 좋은 글

코딩 테스트2024-05-07

2186번 - 문자판

알파벳 문자가 한칸에 하나씩 적혀있는 NxM크기의 문자판이 있다. 임의의 칸에서 시작하여 상하좌우 K개의 칸까지 이동하며 문자를 모은다. 반드시 한 칸 이상 이동하며, 같은 자리에 머물 수 없다. 같은 칸을 여러 번 방문할 수 있다.

코딩 테스트2024-03-18

11657번 - 타임머신

N개의 도시가 있다. 한 도시에서 출발해 다른 도시에 도착하는 버스 M개가 있다. 각 버스는 A,B,C로 나타낸다. A-시작도시, B-도착도시, C-걸리는 시간 C는 양수가 아닐 수 있다.

코딩 테스트2024-02-14

2096번 - 내려가기

n줄에 0이상 9이하의 숫자가 세개씩 적혀있다. 첫줄에서 가장 마지막줄까지 이동하면서 세가지 숫자 중 하나를 고른다. 마지막 줄에서 얻을 수 있는 최대 점수, 최소 점수를 구해라 이 문제는 dp로 풀 수 있겠다고 생각했다.

코딩 테스트2024-02-07

5525번 - IOIOI

n+1개의 I와 n개의 O로 이루어진 문자열이 있다. (IOIOI…) I,O로 이루언진 문자열 S가 주어졌을 때, S안에 위의 문자열이 몇번 포함되어 있는지 구해라 위 코드는 50점을 받았다.

← 서재 목록으로 돌아가기