글 읽기 - BFS를 이용한 풀이 반례를 도저히 못찾겠습니다...

adoo24 2년 전 0

게시판의 반례들 다 대입해봤는데도 이상이 없어서 어디서 틀린건지 감도 안잡히네요,,,

BFS를 통해서 depth가 추가될 때 마다 색을 바꿔서 칠해가주면서 문제가 있는지 확인해주고, 끝나면 색이 안칠해진 노드를 찾아서 BFS를 다시 호출해 주었습니다

그래프 정보는 벡터에 저장시켰구요,,,

고수님들 자비를 베풀어주세요 식음을 전폐하고 있습니다,,,

#include <string>
#include <cstring>
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <tuple>
#include <vector>
#include <queue>
#include <math.h>
#include <sstream>
#include <set>
#include <map>
using namespace std;
int K,V,E,node,ver,tog=0,done=0;
vector<int> info[20001];
bool visited[20001]={false,};
int arr[20001]={-1,};
bool BFS(int n){
    visited[n]=true;
    queue<int> q;
    q.push(n);
    arr[n]=tog;
    tog=tog^1;                                      //색이 칠해질때 마다 0,1로 토글시켜줌
    while(!q.empty()){
        int temp = q.front();
        q.pop();
        for(int i=0;i<info[temp].size();i++){
            if(visited[info[temp][i]]){             //방문했으면 큐에 넣지 않음. 같은색으로 겹치는지 확인만
                if(arr[info[temp][i]]!=tog){
                    return false;                   //겹치면 false반환
                }
            }
            else{
                visited[info[temp][i]]=true;
                arr[info[temp][i]]=tog;
                done=1;                             //색칠하지 않았음에도 토글되는 것 방지
                q.push(info[temp][i]);
            }
        }
        if(done){
            tog=tog^1;
            done--;
        }
    }
    return true;
}
int main(){
    int flag=0;
    cin>>K;
    for(int Q=0;Q<K;Q++){
        memset(arr, -1, sizeof(arr));
        memset(visited,false,sizeof(visited));
        for(int i=0;i<20001;i++){
            info[i].clear();
        }
        cin>>V>>E;
        for(int L=0;L<E;L++){
            cin>>node>>ver;                             //연결된 시작 노드와 끝노드
            info[node].emplace_back(ver);               //시작노드번호 벡터에 끝노드 번호를 저장시킴
        }
        for(int i=1;i<=V;i++){
            if(arr[i]==-1){                             //초기화 상태라면
                if(!BFS(i)){                            //BFS실행을 통해 색칠해줌, false라면 NO 출력
                    cout<<"NO"<<endl;
                    flag=1;
                    break;
                }
            }
        }
        if(flag==0){
            cout<<"YES"<<endl;
        }
        flag=0;
    }
    return 0;
}

fldj2855 2년 전 2

무방향이기 때문에 vector[node]에만 ver를 추가하시면 문제가 생길 수도 있습니다

(그리고 같은 depth에 따라 같은 tog값을 유지하는 과정도 필요해 보입니다)

반례입니다

2
4 4
1 2
1 3
2 4
3 4
4 4
1 2
1 3
2 4
4 3

정답
YES
YES

출력
NO
YES

둘은 같은 그래프임에도 불구하고 출력 결과가 다르게 나오기도 합니다

~~식음을 전폐하느라 하루동안 아무것도 못드셨을 것을 생각하니 많이 안타깝습니다.~~

~~빨리 정답입니다! 를 받으시고 밥을 드시러 가시길 바랍니다..~~

adoo24 2년 전 0

제 거지같은 코드를 봐주시고 반례까지 직접 찾아주시다니,,,, 정말 눈물이 날 것 같습니다 정말 감사합니다 수정해보도록 하겠습니다

고수님 좋은 하루 되세요!!

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

문제

문제

출처

ICPC

BFS를 이용한 풀이 반례를 도저히 못찾겠습니다...

adoo24 2년 전 0

fldj2855 2년 전 2

adoo24 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말