인프런 커뮤니티 질문&답변

안녕하세요 상준님 ㅎㅎ

제 생각에는 can_make_unite`

함수가 계속해서 호출되기 때문에 -> 시간초과가 나는 것 같습니다.

해당 부분을 없애고 + moved 플래그변수 추가 등으로 다듬어봤습니다.

이렇게 해보시겠어요?

#include <bits/stdc++.h>

using namespace std;

int N, L, R;
int m[50][50] = {0};
int dr[] = {-1, 0, 1, 0};
int dc[] = {0, 1, 0, -1};
 
bool can_break_wall(int a, int b) {
    return L <= abs(a - b) && abs(a - b) <= R;
}
 
pair<int, int> make_unite_bfs(int r, int c, int united[][50], int unite_num) {
    int ret1 = 0, ret2 = 0;
    queue<pair<int, int>> q;
    vector<pair<int, int>> alliance; // 연합에 속한 좌표를 기록

    united[r][c] = unite_num;
    q.push({r, c});
    alliance.push_back({r, c});
    ret1++;
    ret2 += m[r][c];

    while (!q.empty()) {
        int row = q.front().first, col = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nr = row + dr[i], nc = col + dc[i];
            if (nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
            if (united[nr][nc] != 0) continue;
            if (!can_break_wall(m[row][col], m[nr][nc])) continue;
            united[nr][nc] = unite_num;
            q.push({nr, nc});
            alliance.push_back({nr, nc});
            ret1++;
            ret2 += m[nr][nc];
        }
    }

    // 연합이 발생한 경우에만 해당 좌표에 새로운 인구수를 할당
    if (ret1 > 1) {
        int new_population = ret2 / ret1;
        for (auto &[row, col] : alliance) {
            m[row][col] = new_population;
        }
    }

    return {ret1, ret2};
}

int main() {
    cin >> N >> L >> R;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> m[i][j];
        }
    }

    int day = 0;
    while (true) {
        int united[50][50] = {0};
        int unite_num = 0;
        bool moved = false;

        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                if (united[r][c] == 0) {
                    auto result = make_unite_bfs(r, c, united, ++unite_num);
                    if (result.first > 1) {
                        moved = true;
                    }
                }
            }
        }

        // 더 이상 인구 이동이 발생하지 않았으면 종료
        if (!moved) break;
        day++;
    }

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

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.