[BOJ] 1707. 이분 그래프 - JAVA

🔗 문제

https://www.acmicpc.net/problem/1707

1707번: 이분 그래프

 

🧩 풀이 및 코드

문제 유형 : 그래프 이론, 그래프 탐색, 너비우선탐색(BFS), 깊이우선탐색(DFS), 이분그래프

 

풀이

이분 그래프란

인접한 정점끼리 서로 다른 색으로 칠해 모든 정점을 두 가지 색으로 칠할 수 있는 그래프이다.

즉, 그래프의 모든 정점이 두 그룹으로 나눠지고 서로 다른 그룹의 정점의 서로 간선으로 연결되어 있지 않은 그래프를 이분 그래프라고 한다.

 

이분그래프 판단은 BFS 또는 DFS 를 통해 판단할 수 있다.

이 문제는 BFS 를 사용해서 풀었다.

 

알고리즘

핵심 : 서로 인접한 정점이 같은 색이면 이분 그래프가 아니다.

• BFS, DFS 로 탐색하며 정점을 방문할 때마다 두 가지 색 중 하나를 칠한다.
• 현재 정점과 인접한 정점을 방문할 땐 자신과 다른 색으로 칠한다.
• 탐색을 진행하다 자신과 같은 색을 칠한 정점을 만나면 이분 그래프가 아니다.
• 주의할 점은 연결 그래프와 비연결 그래프 둘 다 고려해야 한다. 그래프가 비연결 그래프인 경우 모든 정점에 대해서 확인하는 작업이 필요하다.

느낀 점

이거 전에는 못풀었던 건데 쉽게 풀 수 있게 돼서 뿌듯하다

 

전체 코드

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

public class Main_bj_1707_이분그래프 {
	
	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("res/input_bj_1707.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int T = Integer.parseInt(br.readLine());
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		for(int tc=0; tc<T; tc++) {
			st = new StringTokenizer(br.readLine(), " ");
			int V = Integer.parseInt(st.nextToken());
			int E = Integer.parseInt(st.nextToken());
			
			ArrayList<Integer>[] adjList = new ArrayList[V+1];
			for(int i=1; i<=V; i++) {
				adjList[i] = new ArrayList<>();
			}
			
			for(int i=0; i<E; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				
				adjList[a].add(b);
				adjList[b].add(a);
			}
			
			int[] color = new int[V+1];		// 0은 아직 방문하지 않은 정점, 집합 1, -1로 구분
			Arrays.fill(color, 0);
			
			boolean res = true;
			for(int i=1; i<=V; i++) {			// 정점 돌기
				if(color[i] != 0) continue;		// 이미 방문한 정점
				res = BFS(i, color, adjList);
				if(!res) break;
			}
			
			if(res) sb.append("YES").append("\n");
			else sb.append("NO").append("\n");
		}
		System.out.println(sb.toString());
		br.close();
	}
	
	static boolean BFS(int start, int[] color, ArrayList<Integer>[] adjList) {
		color[start] = 1;
		Queue<Integer> que = new ArrayDeque<>();
		que.add(start);
		
		while(!que.isEmpty()) {
			int now = que.poll();
			for(int neighbor : adjList[now]) {
				if(color[neighbor] == color[now]) {	// 이분 그래프가 아님
					return false;
				}
				if(color[neighbor] != 0) continue;
				color[neighbor] = -color[now];
				que.add(neighbor);
			}
		}
		
		return true;
	}

}

 

---

Reference

https://www.acmicpc.net/problem/1707

1707번: 이분 그래프