글 읽기 - 두 코드의 차이를 모르겠는데 하나는 시간초과 하나는 통과입니다.

rhsnqk 2년 전 0

코드를 보시면 위 코드는 초과 아래 코드는 통과입니다.

제가보기엔 그냥 거의 같습니다. 어떤차이로 인해 다른 결과를 내놓는지 모르겠습니다.

make_pair가 느리다는 말이 있어 {}로 고쳐도 안되고 잘 모르겠습니다...

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

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

void bfs(vector<vector<int> > &ground, vector<vector<int> > &unions, int first_y, int first_x, int &cnt, int l, int r) {
    int sum = 0;
        
    vector<pair<int, int> > united;
    united.push_back(make_pair(first_y, first_x));
    
    queue<pair<int, int> > q;
    q.push(make_pair(first_y, first_x));
    
    unions[first_y][first_x] = cnt;
        
    sum += ground[first_y][first_x];
        
    int num = 1;
    
    while(!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
            
        q.pop();
            
        for (int i = 0; i < 4; ++i) {
            int ny = y + dy[i];
            int nx = x + dx[i];
        
            if (ny >= 0 && ny < ground.size() && nx >= 0 && nx < ground[0].size()) {
                if (unions[ny][nx] == -1) {  //이조건 빼먹지 않기 이미 방문한 것을 또 방문하지 않게 !!
                    int diff = abs(ground[ny][nx] - ground[y][x]);
            
                    if (diff >= l && diff <= r) {
                        q.push(make_pair(ny, nx));
                    
                        unions[ny][nx] = cnt;
                        
                        sum += ground[ny][nx];
                        
                        united.push_back(make_pair(ny, nx));
                        
                        ++num;
                    }
                }
            }
        }
    }
        
        
    for (int i = 0; i < united.size(); ++i) {
        int y = united[i].first;
        int x = united[i].second;
            
        ground[y][x] = sum / num;
    }
}

int main() {
    int n, l, r;
    cin >> n >> l >> r;
    
    vector<vector<int> > ground(n, vector<int>(n));
    
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> ground[i][j];
        }
    }
    
    int answer = 0;
    
    while (1) {
        vector<vector<int> > unions(n, vector<int>(n, -1));  //다시검사시 unions 초기화!!!
    
        int cnt = 0;
    
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (unions[i][j] == -1) {
                    bfs(ground, unions, i, j, cnt, l, r);  //이렇게 bfs를 따로 해줘야 위에 bfs처리시 같은 연합끼리 분배하고 나면 dist가 바뀌어있기 떄문에 나머지 노드끼리 연합을 검사할수 있음!!!
                    
                    ++cnt;
                }
            }
        }
        
        if (cnt == n * n) break; // 모든점들이 연합 없이 각각 위의 cnt증가
        
        ++answer;
    }
    
    cout << answer;
    
    return 0;
}

----------------------------------------------------------------------------------------------
    
    #include <bits/stdc++.h>

using namespace std;

// 땅의 크기(N), L, R 값을 입력받기
int n, l, r;

// 전체 나라의 정보(N x N)를 입력받기
int graph[50][50];
int unions[50][50];

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

// 특정 위치에서 출발하여 모든 연합을 체크한 뒤에 데이터 갱신
void process(int x, int y, int index) {
    // (x, y)의 위치와 연결된 나라(연합) 정보를 담는 리스트
    vector<pair<int, int> > united;
    united.push_back({x, y});
    // 너비 우선 탐색 (BFS)을 위한 큐 라이브러리 사용
    queue<pair<int, int> > q;
    q.push({x, y});
    unions[x][y] = index; // 현재 연합의 번호 할당
    int summary = graph[x][y]; // 현재 연합의 전체 인구 수
    int count = 1; // 현재 연합의 국가 수
    // 큐가 빌 때까지 반복(BFS)
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        // 현재 위치에서 4가지 방향을 확인하며
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            // 바로 옆에 있는 나라를 확인하여
            if (0 <= nx && nx < n && 0 <= ny && ny < n && unions[nx][ny] == -1) {
                // 옆에 있는 나라와 인구 차이가 L명 이상, R명 이하라면
                int gap = abs(graph[nx][ny] - graph[x][y]);
                if (l <= gap && gap <= r) {
                    q.push({nx, ny});
                    // 연합에 추가하기
                    unions[nx][ny] = index;
                    summary += graph[nx][ny];
                    count += 1;
                    united.push_back({nx, ny});
                }
            }
        }
    }
    // 연합 국가끼리 인구를 분배
    for (int i = 0; i < united.size(); i++) {
        int x = united[i].first;
        int y = united[i].second;
        graph[x][y] = summary / count;
    }
}

int totalCount = 0;

int main(void) {
    cin >> n >> l >> r;

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

    // 더 이상 인구 이동을 할 수 없을 때까지 반복
    while (true) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                unions[i][j] = -1;
            }
        }
        int index = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (unions[i][j] == -1) { // 해당 나라가 아직 처리되지 않았다면
                    process(i, j, index);
                    index += 1;
                }
            }
        }
        // 모든 인구 이동이 끝난 경우
        if (index == n * n) break;
        totalCount += 1;
    }

    // 인구 이동 횟수 출력
    cout << totalCount << '\n';
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

두 코드의 차이를 모르겠는데 하나는 시간초과 하나는 통과입니다.

rhsnqk 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말