글 읽기 - 시간초과 질문 드립니다

kyb1208tg 1년 전 0

bfs를 사용해서 풀었고 그룹끼리 크기를 구해놓고 map값이 1일때 주변에 있는 그룹을 확인하고 그룹크기를 더해서 출력하도록했습니다.

계속 시간초과가 나오는데 어느부분에서 더 줄일수 있을까요?

#include<cstring>
#include<iostream>
#include<queue>
#include<cstdio>
#include<algorithm>
#include<tuple>
using namespace std;
int map[1000][1000];
int dist[1000][1000];
int group[1000][1000];
int group_size[500000];
int group_check[500000];
int dx[]={0,0,-1,1};
int dy[]={-1,1,0,0};
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            scanf("%1d",&map[i][j]);
            dist[i][j]=-1;
        }
    }
    int g_number=1;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(dist[i][j]==-1&&map[i][j]==0){
                queue<pair<int,int>> q;
                q.push(make_pair(i,j));
                dist[i][j]=0;
                group[i][j]=g_number;
                int cnt=1;
                while(!q.empty()){
                    int x,y;
                    tie(x,y)=q.front(); q.pop();
                    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<m){
                            if(dist[nx][ny]==-1&&map[nx][ny]==0){
                                q.push(make_pair(nx,ny));
                                dist[nx][ny]=dist[x][y]+1;
                                group[nx][ny]=g_number;
                                cnt+=1;
                            }
                        }
                    }
                }
                group_size[g_number]=cnt;
                g_number+=1;
            }
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(map[i][j]==1){
                int ret=1;
                memset(group_check,-1,sizeof(group_check));
                for(int z=0;z<4;z++){
                    int nx=i+dx[z];
                    int ny=j+dy[z];
                    if(0<=nx&&nx<n&&0<=ny&&ny<m){
                        int g=group[nx][ny];
                        if(group_check[g]==-1){
                            ret+=group_size[g];
                            group_check[g]=1;
                        }
                    }
                }
                cout<<ret;
            }
            else{
                cout<<map[i][j]%10;
            }
        }
        cout<<"\n";
    }
}

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

문제

문제

출처

ICPC

시간초과 질문 드립니다

kyb1208tg 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말