글 읽기 - bfs 구현 문제

jbh332 4년 전 0

dfs는 정답으로 나오는데 bfs에서는 틀렸다고 나오네요

bfs 구현과정에 문제가 있는 것 같은데 어디가 문제죠..?

import java.util.*;

public class Main{ 
    
    static void bfs(ArrayList<Integer>[] a, int[] color, int x, int c) {
     Queue<Integer> q = new LinkedList<Integer>();
     q.add(x);
     color[x] = c;
     while(!q.isEmpty()) {
      int y = q.remove();
      for(int z : a[y]) {
       if(color[z] == 0) {
        color[z] = 3-c;
           q.add(z);
           c = 3-c;
          }
      }
      
     }
    }
    
    static void dfs(ArrayList<Integer>[] a, int[] color, int x, int c){
        color[x] = c;
        for(int y : a[x]){
            if(color[y] == 0){
                dfs(a, color, y, 3-c); // 3-c 인 이유 > 0 : 방문x 1 : A 그룹 2 : B그룹
            }
        }
    }
    
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        
        while(k-- > 0){
            int n = sc.nextInt();
            int m = sc.nextInt();
            int[] color = new int[n+1];
            boolean ok = true;
            ArrayList<Integer>[] a = new ArrayList[n+1];
            for(int i = 1; i <= n; i++){
                a[i] = new ArrayList<Integer>();
            }
            
            for(int i = 0; i < m; i++){ // 인접리스트 구현
                int from = sc.nextInt();
                int to = sc.nextInt();
                a[from].add(to);
                a[to].add(from);
            }
            
            
            for(int i = 1; i <= n; i++){ 
                if(color[i] == 0){
                    dfs(a, color, i, 1);
                    //bfs(a, color, i, 1);
                }
            }
            
            for(int i = 1; i <= n; i++){
                for(int j : a[i]){
                    if(color[i] == color[j]){ // 간선으로 연결된 노드는 같은 색이면 안됨
                        ok = false;
                    }
                }
            }
            if(ok){
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
            
            
        }
    }
}

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

문제

문제

출처

ICPC

bfs 구현 문제

jbh332 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말