Do it! 알고리즘 코딩 테스트 (48번)

48번 이분 그래프

---

내가 떠올린 풀이 해설

이 문제를 해결하려면 이분 그래프의 대한 이해가 필요하다.

이분 탐색 블로그 : https://hongjw1938.tistory.com/117

자료구조 - 이분 그래프(Bipartite Graph)

그래프를 인접 리스트로 구현한다. 모든 노드로 각각 DFS 알고리즘을 적용해 수행한다. DFS를 실행할 때 현재 노드에서 연결된 노드 중 이미 방문한 노드가 나와 같은 집합이면 이분 그래프가 아닌 것으로 판별한다. 실행 결과가 이분 그래프가 아니면 이후 노드는 탐색하지 않는다. DFS를 사용하는 이유는 그래프의 모든 노드가 이어져있지 않고, 여려 개의 부분 그래프로 이뤄진 케이스가 존재할 수 있기 때문이다.

---

정확한 풀이

import java.io.*;
import java.util.*;
public class Baek1707 {
	static ArrayList<Integer> list[];
	static int[] check;
	static boolean visit[];
	static boolean IsEven;
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		for(int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int v = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			
			list = new ArrayList[v + 1];
			visit = new boolean[v + 1];
			check = new int[v + 1];
			IsEven = true;
			for(int j = 1; j <= v; j++) {
				list[j] = new ArrayList<>();
			}
			for(int j = 0; j < e; j++) {  // 인접 리스트로 그래프 저장하기 
				st = new StringTokenizer(br.readLine());
				int start = Integer.parseInt(st.nextToken());
				int end = Integer.parseInt(st.nextToken());
				list[start].add(end);
				list[end].add(start);
			}
			// 주어진 그래프가 1개로 연결돼 있다는 보장이 없으므로 모든 노드에서 수행하기 
			for(int j = 1; j <= v; j++) {
				if(IsEven) {
					DFS(j);
				}
				else {
					break;
				}
			}
			check[1] = 0;
			if(IsEven) {
				System.out.println("YES");
			}
			else {
				System.out.println("NO");
			}
		}
	}

	private static void DFS(int node) {
		visit[node] = true;
		for(int i : list[node]) {
			if(!visit[i]) {
				// 인접한 노드는 같은 집합이 아니므로 이전 노드와 다른 집합으로 처리하기 
				check[i] = (check[node] + 1) % 2;
				DFS(i);
			}
			// 이미 방문한 노드가 현재 내 노드와 같은 집합이면 이분 그래프가 아
			else if(check[node] == check[i]){
				IsEven = false;
			}
		}
	}
}

---

오늘의 회고

오늘은 긴 연휴가 끝나고 시작하는 하루입니다. 연휴동안 잘 쉬고 놀았으니 다시 힘내서 나아가 보겠습니다. 그래프 한 문제를 풀고 주말에 하지 못한 복습을 Do it! 알고리즘 코딩테스트(14번) 까지 진행하였습니다.