Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

24. DFS와 BFS

그래프를 순회하는 알고리즘을 배워 봅시다.

Java / Python

11. 이분 그래프

1707번

그래프 순회를 통해 이분 그래프를 판별하는 문제

이번 문제는 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 이 그래프를 이분 그래프 (Bipartite Graph) 라 부르는 데, 그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하는 문제입니다.

이분 그래프는 어떤 한 정점에서 연결된 모든 다른 정점이 다른 값을 가져야하는 그래프라고 합니다.
BFS 탐색을 이용했습니다.

• Java

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

public class Main {
	static int V, E;
	static ArrayList<ArrayList<Integer>> graph;
	static int[] check;
    
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));   
		
		int T = Integer.parseInt(br.readLine());

		while (T-- > 0) {
			StringTokenizer st = new StringTokenizer(br.readLine());            
			V = Integer.parseInt(st.nextToken());
			E = Integer.parseInt(st.nextToken());
            
			check = new int[V+1];
			graph = new ArrayList<>();
			
			for(int i = 0; i <= V; i++)
				graph.add(new ArrayList());
            
			for(int i = 0; i < E; i++){
				st = new StringTokenizer(br.readLine());
				int p1 = Integer.parseInt(st.nextToken());
				int p2 = Integer.parseInt(st.nextToken());
                
				graph.get(p1).add(p2);
				graph.get(p2).add(p1);
			}
			boolean flag = true;
			for (int i = 1; i <= V; i++){
				if(check[i] == 0){
					if(!bfs(i, E)){
						flag = false;
						break;
					}
				}
			} 
			if(flag)
				bw.write("YES\n");
			else
				bw.write("NO\n");
		}       
		bw.flush();
		bw.close();
		br.close();
	}

	public static boolean bfs(int start, int e) { 
		Queue<Integer> queue = new LinkedList<>();

		queue.add(start);
		check[start] = 1;

		while (!queue.isEmpty() && e-- >= 0) {
			int now = queue.poll();
                
			for (int next : graph.get(now)) {
				if(check[next] == 0){
					queue.offer(next);
					check[next] = (check[now] == 1) ? 2 : 1;                        
				}
				if(check[now] == check[next]){
					return false;
				}                                 
			}
		}
		return true;
	}
}

• Python

from collections import deque
import sys
T = int(sys.stdin.readline())

# bfs 경로 탐색
def bfs(start):
    queue = deque()
    queue.append(start)
    check[start] = 1
    while queue:
        a = queue.popleft()
        for i in arr[a]:
            if check[i] == 0:
                check[i] = -check[a]
                queue.append(i)
            else:
                if check[i] == check[a]:
                    return False
    return True

for i in range(T):
    V, E = map(int, sys.stdin.readline().split())
    isTrue = True
    arr = [[] for i in range(V + 1)]
    check = [0 for i in range(V + 1)]
    for j in range(E):
        a, b = map(int, sys.stdin.readline().split())
        arr[a].append(b)
        arr[b].append(a)
    for k in range(1, V + 1):
        if check[k] == 0:
            if not bfs(k):
                isTrue = False
                break
    print("YES"if isTrue else "NO")