글 읽기 - c++ 시간초과 질문입니다.

hw0404 2년 전 0

시간초과가 났는데 그 이유를 못찾겠습니다.

그리고 중간에 제가 result, stop_cnt M_result 이런 변수들을 사용해서 조건에 맞는 출력 나오게했는데

이런식으로 코딩을 하는게 괜찮은건지 궁금합니다.

고수님들 도와주세요!!

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

using namespace std;

#define MAX_N 51
int N , M; // 연구소 크기와 바이러스의 갯수
int stop=0;
int map[MAX_N][MAX_N];  //연구소 지도
int x_dir[4]={-1,1,0,0};
int y_dir[4]={0,0,-1,1};
queue<pair<int,int>> q;
queue<pair<int,int>> loca_virus;
vector<pair<int,int>>v;
int arr[11];
int visit[MAX_N][MAX_N];
int visited[10];
int cnt[MAX_N][MAX_N];
int result =0;
int M_result =99999 ;
int stop_cnt =0;

void bfs();
void bruto(int num);

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> N >> M;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            int input;
            cin >> input;
            map[i][j]=input;
            if(input ==0 ) stop +=1;
            else if(input ==2){
                loca_virus.push(make_pair(i,j));
                v.push_back(make_pair(i,j));
                }
        }
    }
    //움직일 수 있는 칸이 없을 때

    if(stop ==0 ){
        cout<< 0 <<"\n";
        return 0;
    }
    else{
        bruto(0);
        if(M_result == 99999) {
            cout << -1;
       }
       else
        cout<<M_result;
        
    }
    return 0 ;
}
void bfs(){
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        visit[x][y]=1;
        for(int i=0;i<4;i++){
            int nx = x + x_dir[i];
            int ny = y + y_dir[i];
            if(nx >=0 && ny >= 0 && nx < N && ny < N){
                if( map[nx][ny]==0){
                        if(visit[nx][ny]==0){
                            visit[nx][ny]=1;
                            cnt[nx][ny]=cnt[x][y]+1;
                            stop_cnt+=1;
                            result = cnt[nx][ny];
                            q.push(make_pair(nx,ny));
                    }
                }
            }
        }
    }
}

void bruto(int num){
    //바이러스의 갯수만큼 일때
    
    if(num == M){
        for(int i=0;i<M;i++){
            q.push(make_pair(v[arr[i]].first,v[arr[i]].second));
        }
        bfs();
        memset(cnt, 0, sizeof(cnt));
        memset(visit,0,sizeof(visit));
        if(stop_cnt==stop){
            if(result < M_result){
                M_result = result;
            }
        }
        stop_cnt =0;
        return;
    }
    for(int i=0;i<v.size();i++){
        if(visited[i]==0){
            visited[i]=1;
            visit[v[i].first][v[i].second]=1;
            arr[num]=i;
            bruto(num+1);
            visited[i]=0;
        }
    }
}

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

문제

문제

출처

ICPC

c++ 시간초과 질문입니다.

hw0404 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말