글 읽기 - 속도 개선 문제

wjm358 4년 전 0

맞으신분들 보니까 제 코드와 비슷하게 하신분들도 100ms 내외로 나오시던데 저는 400ms가 나옵니다..

채점하는 과정에서 보니까 78~80%사이에서 연산이 많이 들어가던데 혹시 가지치기 같은것에 걸려서 느리게 나오는건지 궁금합니다 ㅠ

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<string.h>


using namespace std;
typedef pair<int,int> pp;

int map[51][51];
bool v[51][51];
int dx[] ={0,1,0,-1}, dy[] = {1,0,-1,0};
int n , l, r;
int ans =0 ;

bool inside(int nx, int ny) {
    return nx>= 0 && nx < n && ny >= 0 && ny <n;
}

bool bfs(int i,int j){
    
                int cnt =0 ;
                int sum =0 ;
                queue<pp> q;
                vector<pp> open;
                
                q.push(make_pair(i,j));
                v[i][j] =true;
                open.push_back(make_pair(i,j));
                cnt++; sum += map[i][j];
            
                while(!q.empty()) {
                    int x = q.front().first;
                    int y = q.front().second;
                    q.pop();

                    for(int k=0; k<4;k++) {
                        int nx = x + dx[k];
                        int ny = y + dy[k];
                        if(!inside(nx,ny)) continue; 
                         if(v[nx][ny]) continue;
                            else {
                                int diff = abs(map[x][y] - map[nx][ny]);
                                if(diff >= l && diff <= r) {
                                v[nx][ny] = true;
                                q.push(make_pair(nx,ny));
                                open.push_back(make_pair(nx,ny));
                                cnt++; sum += map[nx][ny];  }
                            }
                        
                    }
                }

        if(cnt <= 1) {return false; }
        else {
           
            int divide = sum / cnt; 
            int len = open.size();
            for(int i=0; i<len;i++) 
                map[open[i].first][open[i].second] = divide;
            return true;
        }
}
int main() {
    cin >> n >> l >> r;
    for(int i=0; i<n;i++) {
        for(int j=0; j<n;j++) {
           scanf("%d",&map[i][j]);
        }
    }

    while(1) {
        
        bool is_exist = false;
        for(int i=0; i<n;i++) {
            for(int j=0; j<n;j++)   
                v[i][j]= false;
        }
        for(int i=0; i<n;i++) {
            for(int j=0; j<n;j++) {
                if(v[i][j] ) continue;
                if(bfs(i,j)) {
                    is_exist = true;
                }
     }
   }
        //이중 for문 종료

        if(is_exist == false) break;
        ans++;

    }
    cout << ans << endl;
}

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

문제

문제

출처

ICPC

속도 개선 문제

wjm358 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말