백준 16234 인구이동

작성일 | In |

Problem : 인구이동

유형 : 시뮬레이션, BFS

문제 해석

  • 인구 이동의 횟수를 구하라

문제 재해석

  • 연합이 만들어진 횟수를 구하라.

해결 전략 (15)

  • 한 나라씩 전부 BFS를 진행한다.
  • 한번이라도 연합이 만들어 졌다면, 인구 이동이 일어난 것으로 한다.

설계 (5), 구현 (20)

  • 방문하지 않았던 나라라면, 큐에 넣고 BFS를 진행한다.
  • BFS중 큐에 들어갔던 나라들은 연합을 이루는 나라이다.
  • 연합을 구성하는 나라가 1개라면 연합 구성에 실패했다.
  • 연합을 구성하는 나라가 2개 이상이라면, 평균 값을 대입해준다.

주의할 점

  • 소수점은 버린다.
  • 모든 나라에 대해서 BFS 를 시도 한뒤, 방문 표시를 초기화 해주어야 한다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <bits/stdc++.h>
#define pp pair<int,int>
#define x first
#define y second

using namespace std;

int n, L, R;

int board[52][52];
bool visit[52][52];

const int dx[] = { -1,1,0,0 };
const int dy[] = { 0,0,-1,1 };


queue<pp> q;

bool bfs() {
    queue<pp> team_q;
    int team_cnt = 0;
    int sum = 0;
    
    while (!q.empty()) {
        pp cur = q.front(); q.pop();
        team_q.push(cur);

        team_cnt++;
        sum += board[cur.x][cur.y];

        int cur_humans = board[cur.x][cur.y];

        for (int dir = 0; dir < 4; ++dir) {
            int nx = cur.x + dx[dir];
            int ny = cur.y + dy[dir];

            if(nx < 0 or nx >= n or ny < 0 or ny >= n) continue;
            if (visit[nx][ny]) continue;

            int nxt_humans = board[nx][ny];
            int diff = abs(cur_humans - nxt_humans);
            if (diff < L or diff > R) continue;

            visit[nx][ny] = true;
            q.push({ nx,ny });

        }
    }
    

    if (team_cnt == 1) return false;
    
    int avg = sum / team_cnt;

    while (!team_q.empty()) {
        pp cur = team_q.front(); team_q.pop();
        board[cur.x][cur.y] = avg;
    }

    return true;
}

void solve() {
    int human_move = 0;

    while (1) {
        bool moved = false;

        for (int i = 0; i < n; ++i) {
            for (int ii = 0; ii < n; ++ii) {
                if (visit[i][ii])continue;
                visit[i][ii] = true;
                q.push({ i,ii });

                if (bfs()) moved = true;
            }
        }

        if (moved)  human_move++;
        else break;

        memset(visit, false, sizeof(visit));
    }

    cout << human_move << "\n";
}

void input() {
    cin >> n >> L >> R;

    for (int i = 0; i < n; ++i) {
        for (int ii = 0; ii < n; ++ii) {
            cin >> board[i][ii];
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);
    freopen("input.txt", "r", stdin);

    input();
    solve();

    return 0;
}

피드백

  • 문재 해석에 시간이 걸렸다.
  • 평균값 대입해주는 while 문에서 실수 했었다. 디버깅 3분 소요