글 읽기 - 어느 부분이 잘못되었길래 시간초과가 나나요?

nmp9981 2년 전 0

1번부터 시작해 깊이 우선탐색으로 레드팀을 정하고 블루팀을 탐색한뒤 두 팀이 모두 연결된지 확인뒤 답을 구했습니다.

아마 dfs부분에서 시간초과가 나는것 같은데 맞나요?

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

int n,total;
const int maxi = 11;
const int inf = 100000;
bool visit_red[maxi];//방문기록 체크
bool visit_blue[maxi];//방문기록 체크
int people[maxi];//인구수
vector<int> area[maxi];//벡터
int ans = inf;

//입력
void input(){
    cin>>n;
    //인구수 입력
    for(int i=1;i<=n;i++){
        cin>>people[i];
        total+=people[i];
    }
    //그래프 입력
    for(int i=1;i<=n;i++){
        int m;
        cin>>m;
        while(m--){
            int a;
            cin>>a;
            area[i].push_back(a);//양방향 그래프
            area[a].push_back(i);
        }
    }
} 
//연결되었는가?
void bfs(){
    memset(visit_blue,false,sizeof(visit_blue));//초기화
    queue<int> q;
    int red_human = 0;
    //탐색 시작지점
    for(int i=1;i<=n;i++){
        if(visit_red[i]==false){
            visit_blue[i] = true;//방문체크
            q.push(i);
            break;
        }
    }
    while(!q.empty()){
        int x = q.front();
        q.pop();
        
        //다음노드
        for(int i=0;i<area[x].size();i++){
            int nx = area[x][i];
            //어느팀에도 속하지 않는다.
            if(visit_blue[nx]==false && visit_red[nx]==false){
                visit_blue[nx] = true;
                q.push(nx);
            }
        }
    }
    //두 팀을 모두 이루는가?
    bool team_flag = true;
    for(int i=1;i<=n;i++){//둘중하나는 소속되어 있어야함
        if(visit_blue[i]==false && visit_red[i]==false){
            team_flag = false;
            break;
        }
    }
    //팀을 이루면
    if(team_flag==true){
        //레드팀 합
        for(int i=1;i<=n;i++){
            if(visit_red[i]==true){
                red_human+=people[i];
            }
        }
        int blue_human = total-red_human;
        ans = min(ans,abs(blue_human-red_human));
    }
}
//깊이 우선 탐색
void dfs(int node,int cnt){
    //끝까지 탐색
    if(cnt==n-1){
        return;
    }
    //다음지점 탐색
    for(int i=0;i<area[node].size();i++){
        int next_node = area[node][i];//다음지점
        visit_red[next_node] = true;//방문체크
        bfs();//이분그래프를 이루는가?
        dfs(next_node,cnt+1);//다음지점
        visit_red[next_node] = false;//방문해제
    }
}
int main(){
    input();//입력
    //1번은 레드팀
    visit_red[1] = true;//방문체크
    ans = total-people[1];
    dfs(1,1);//1번을 기준으로 깊이 우선 탐색
    //출력
    if(ans==inf){//나눌 수 없다.
        cout<<-1;
    }else{
        cout<<ans;
    }
    return 0;
}

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

문제

문제

출처

ICPC

어느 부분이 잘못되었길래 시간초과가 나나요?

nmp9981 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말