글 읽기 - 75프로에서 틀립니다... 도와주세요..ㅠㅠ

konduck196 2년 전 0

안녕하세요

BFS로 문제를 풀고 있습니다.

하나의 노드가 속할 수 있는 color로는 1과 -1로 하였고 , 각 노드의 색을 확인하기 위한 color table은 0으로 초기화하는 것으로 하였습니다.

그래프는 인접리스트로 구현하였습니다.

1. 모든 노드를 전체탐색하며, 아직 color가 부여되지 않은 노드부터 BFS탐색을 시작합니다.

2. BFS를 진행하며 , 큐에서 꺼낸 현재노드의 인접노드에서는 다음을 확인합니다.

2.1 현재노드와 같은 색을 이미 가진 경우 --> return false

2.2.현재노드와 다른 색을 이미 가진 경우 --> continue

2.3 아직 아무런 색이 부여되지 않은 경우 --> 큐에 추가 && 현재 노드색의 반대 색을 부여

3. BFS탐색결과 false가 리턴이 되면, 전체탐색도 멈추고, 해당 케이스는 NO를 출력하게 됩니다.

3-1. 모든 노드에 대해, BFS탐색결과에서 false가 한 번도 리턴된 적 없다면 flag는 true이기 때문에, 해당 케이스는 YES를 출력하게 됩니다.

ㅠㅠ 제 눈으로는 더이상 버그 탐색을 못하는 것 같습니다.. 도움이 필요합니다

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class Main {
    public static int k; // test case 수
    public static int v; // 정점의 수
    public static int e; // edge의 수
    public static int[] color;
    public static ArrayList<Integer>[] graph = new ArrayList[20001];

    public static void main(String[] args) throws IOException{
        Setting();

    }
    public static void Setting() throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        k = Integer.parseInt(br.readLine());
        int v1=0,v2=0;


        for(int test=0;test<k;test++){
            // Test case 정보를 받기 시작 한다.
            st = new StringTokenizer(br.readLine());
            v = Integer.parseInt(st.nextToken());
            e = Integer.parseInt(st.nextToken());

            // init graph
            for(int i=1;i<=v;i++){
                graph[i] = new ArrayList<>();
            }
            // init color
            color = new int[v+1];

            // edge 정보를 받는다.
            for(int i=0;i<e;i++){
                st = new StringTokenizer(br.readLine());
                v1 = Integer.parseInt(st.nextToken());
                v2 = Integer.parseInt(st.nextToken());
                graph[v1].add(v2);
                graph[v2].add(v1);
            }
            solve();
        }

    }
    public static void solve(){
        boolean flag = true;
        for(int i=1;i<=v;i++){
            if(color[v]==0){
                if(bfs(v)) continue;
                else {
                    flag = false;
                    break;
                }
            }
        }
        if(flag) System.out.println("YES");
        else System.out.println("NO");
    }
    // start node passed by arg
    public static boolean bfs(int s){
        Deque<Integer> q = new LinkedList<>();
        q.add(s);
        color[s]=1;
        while(q.isEmpty()==false){
            int cur = q.poll();
            int curColor = color[cur];
            // nextColor = curColor*(-1);
            for (Integer integer : graph[cur]) {
                if(color[integer]==curColor*(-1)) continue;
                // 인접노드가 현재 노드와 같은 색을 할당받은 경우 --> false를 return한다.
                if(color[integer]==curColor) return false;
                // 방문한 적 없는 노드의 경우
                if(color[integer] ==0){
                    q.add(integer);
                    color[integer] = curColor*(-1);
                }
            }
        }
        return true;
    }
}

cjhgg2 2년 전 0

53, 54 번째 줄에서 v를 i로 바꿔보세요

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