<백준> 1707번 자바 알고리즘 [BFS][이분 그래프]

import java.util.*;
import java.io.*;


public class Main
{
    static int v, e; // 정점, 간선 
    static ArrayList<Integer>[] al; // 연결 정보 저장
	static int visit[]; // 초기화 0, 이후 1 or 2 

	public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stz = new StringTokenizer(br.readLine());
        int t = Integer.parseInt(stz.nextToken());
        
        for(int i=0; i<t; i++){
            stz = new StringTokenizer(br.readLine());
            v = Integer.parseInt(stz.nextToken());
            e = Integer.parseInt(stz.nextToken());
            visit = new int[v + 1];
            al = new ArrayList[v + 1];
            
            // 간선 개수 만큼 al 만들기 
            for(int j=0; j <= v; j++){
                al[j] = new ArrayList<>();
            }
            
            // al에 정보 입력하기 
            for(int k=0; k < e; k++){
                stz = new StringTokenizer(br.readLine());
                int p1 = Integer.parseInt(stz.nextToken());
                int p2 = Integer.parseInt(stz.nextToken());
                
                al[p1].add(p2);
                al[p2].add(p1);
            }
            
            bfs();
            
        }
	
	}
	private static void bfs() {
	    Queue<Integer> q = new LinkedList<>();
	    for(int i = 1; i <= v; i++){
	        if(visit[i] == 0){
	            visit[i] = 1;
	            q.add(i);
	        }
	        
	        while(!q.isEmpty()){
	            int now = q.poll();
	            
	            // now 의 al 정보 탐색 
	            for(int j=0; j < al[now].size(); j++){
	                // 만약 0이다 => 반대편 색깔로 만들어 주기 
	                if(visit[al[now].get(j)] == 0){
	                    q.add(al[now].get(j));
	                    if(visit[now] == 1){
	                        visit[al[now].get(j)] = 2;
	                    } else if (visit[now] == 2){
	                        visit[al[now].get(j)] = 1;
	                    }
	                }
	                else if(visit[al[now].get(j)] == visit[now]){
	                    System.out.println("NO");
	                    return;
	                }
	                
	            }
	        }
	    }
	    System.out.println("YES");
	}
}

 

생각 정리 

 

bfs로 어떻게 

일단 현재 점 기준으로 
다음 정점 방문 할 때 인접한 정점이면 다른 색 
=> 인접한 정점인지 어떻게 판별하지 
colors = new int []
red = 1 
blue = 2

queue 를 활용한 bfs 


arraylist에 연결된 정점 입력 ex) 1 3 => al[1] = 3, al[3] = 1

queue에 무엇을 집어 넣음?
1인지 2인지 확인하도록 
일단 초기화 1 집어넣음