글 읽기 - C++ 80%에서 계속 시간초과...

jsh4701 2년 전 0

DFS나 코드 부분 어디를 고쳐야 더 슬림해질 수 있을까요...

#include <bits/stdc++.h>

using namespace std;

int N, L, R;
vector<vector<int>> GO;
int check[50][50] = {0,};
int labelling;
// 1. screen to figure out which points to merge and divide(DFS)
// 2. 각 좌표 값 갱신
// 3. 1번 반복, 만약에 screen시 할 포인트 없음 종료.



void DFS(int m, int n, int label){ // clustering
    for(int k=0; k<4; k++){
        int dx[4] = {-1,0,1,0};
        int dy[4] = {0,-1,0,1};
        int nm = m+dx[k], nn = n+dy[k];
        int comp = abs(GO[nm][nn]-GO[m][n]);
        if(0<=nm && nm<N && 0<=nn && nn<N && !check[nm][nn] && comp >=L && comp<=R){
                check[nm][nn] = label;
                DFS(nm, nn, label);
        }
    }
}

void Screening(){ // labelling 
    labelling = 1;
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            if(!check[i][j]){
                check[i][j] = labelling;
                DFS(i, j, labelling++);
            }
        }
    }
}

void Average(){ // Merge and divide
    for(int l = 1; l<labelling; l++){
        int sum = 0, cnt = 0;
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                if(check[i][j] == l){
                    sum += GO[i][j];
                    cnt++;
                }
            }
        }
        int value = sum/cnt;
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                if(check[i][j] == l){
                    GO[i][j] = value;
                }
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> N >> L >> R;
    
    GO.resize(N);
    for(int i=0; i<N; i++){
        GO[i].resize(N);
        for(int j=0; j<N; j++){
            cin >> GO[i][j];
        }
    }
    
    int days = 0;
    while(true){
        memset(check, 0, sizeof(check));
        Screening(); 
        if(labelling == N*N+1){
            break;
        }
        Average();
        days++;
    }
    
    cout << days;
    return 0;
}

samgkgkgk 2년 전 0

dfs가 아닌 bfs로 풀면 해결될것같습니다!

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

문제

문제

출처

ICPC

C++ 80%에서 계속 시간초과...

jsh4701 2년 전 0

samgkgkgk 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말