글 읽기 - [C++] 80%에서 시간초과가 납니다.

myju742 3년 전 0

채점을 하다 80%정도에서 시간초과가 발생하는데.. 어떻게 해야 시간을 줄일 수 있을지 모르겠네요. 시간복잡도가 O(2000* n^2)인 것 같은데.. 시간복잡도 분석 방법을 더 익히고 와야 할까요?

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;

const int MAX_N = 51;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
bool visited[MAX_N][MAX_N];
int popul[MAX_N][MAX_N];
vector<int> adj[MAX_N*MAX_N];
int n, l, r;

inline int p2i(int x, int y){ return x * n + y;}    // 순서쌍을 adj의 index로 넣어주기 위한 함수
inline pair<int, int> i2p(int i){ return make_pair(i/n, i%n);}  // adj의 index를 순서쌍으로 바꿔주기 위한 함수

vector<int> bfs(int x, int y){ 
    // (x, y)와 연합을 이루는 칸들을 벡터로 반환
    vector<int> ret;
    queue<int> q;
    q.push(p2i(x, y));
    visited[x][y] = true;
    ret.push_back(p2i(x,y));
    while(!q.empty()){  // BFS
        int current = q.front();
        int cx = i2p(current).first, cy = i2p(current).second;
        q.pop();
        for(int i: adj[current]){
            if(!visited[i2p(i).first][i2p(i).second]){
                q.push(i);
                visited[i2p(i).first][i2p(i).second] = true;
                ret.push_back(i);
            }
        }
    }
    return ret;
}


bool action(){
    // adjacency graph 초기화
    for(int i = 0; i < MAX_N * MAX_N; ++i){
        adj[i].clear();
    }
    // adjacency graph 생성
    for(int i = 0; i < n; ++i){
        for(int j = 0; j< n; ++j){
            for(int k = 0; k < 4; ++k){
                int x = i + dx[k], y = j + dy[k];
                if(x < 0 || x >= n || y < 0 || y >= n) 
                    continue;
                int diff = abs(popul[i][j] - popul[x][y]);
                if(l <= diff && diff <= r){
                    adj[p2i(i, j)].push_back(p2i(x, y));
                }
            }
        }
    }
    for(int i = 0;i<MAX_N;++i){
        for(int j = 0;j<MAX_N;++j)
            visited[i][j]=false;
    }
    // BFS를 사용해 연합 찾기
    bool changed = false;   // 인구 상태가 변화하고 있는지 여부
    while(true){
        // 방문하지 않은 칸을 하나 찾기(즉, 지금까지 발견한 연합 모두에 속하지 않은 칸)
        int x = -1, y = -1;
        for(int i = 0; i < n * n; ++i){
            int cx = i2p(i).first; 
            int cy = i2p(i).second;
            if(!(visited[cx][cy])){
                x = cx, y = cy;
                break;
            }
        }

        if(x == -1 && y == -1) break; // 모든 칸을 방문했다면 인구이동 과정 종료
        vector<int> unions = bfs(x, y); // (x, y)와 연합한 나라들
        int sum = 0;
        for(int i: unions){
            int cx = i2p(i).first, cy = i2p(i).second;
            sum += popul[cx][cy];
        }
        int newPop = sum / (unions.size());
        for(int i: unions){
            int cx = i2p(i).first, cy = i2p(i).second;
            if (popul[cx][cy] != newPop)
                changed = true;
            popul[cx][cy] = newPop;
        }
    }
    return changed;
}

int main(){
    
    scanf("%d %d %d", &n, &l, &r);
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j){
            scanf("%d", &popul[i][j]);
        }
    }

    bool changed = true;
    int cnt = 0;
    while(true){
        changed = action();
        if(!changed)break;
        cnt++;
    }
    printf("%d", cnt);
    return 0;
}

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

문제

문제

출처

ICPC

[C++] 80%에서 시간초과가 납니다.

myju742 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말