BOJ 1707 이분그래프 java 자바 bfs dfs 두 가지 방법

BOJ 1707 이분그래프 java 자바 bfs dfs 두 가지 방법

 

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

1707번: 이분 그래프

 

문제에서 설명하는 이분 그래프를 이해하지 못했었다.

개념만 알면 쉽게 풀 수 있다.

두 그룹으로 나눴을 때 자신의 그룹에는 접근할 수 없어야 한다.

예로 들어 a팀인 1번 노드의 인접한 2번 노드로 갔을 때 2번 노드가 a팀이면 안 된다.

 

그래서 dfs 든 bfs 든 같은 맥락으로 

시작점에 1팀을 부여했다면 인접한 노드에는 2팀을 부여한다.

만약 1번 노드에서 2번 노드로 가는데 이미 같은 팀이 부여되어 있다면 바로 NO 하면 된다.

 

끊어진 그래프 경우가 있으니 main 에서 dfs 혹은 bfs 를 호출할 때 visited 배열을 체크하여 방문하지 않은 노드는 또 들어가게 한다.

 

1. dfs

package Baekjoon;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class BOJ_1707_이분그래프 {
	static List<Integer>[] adjList;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int K = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		for (int t = 0; t < K; t++) {
			st = new StringTokenizer(br.readLine());
			int V = Integer.parseInt(st.nextToken());
			int E = Integer.parseInt(st.nextToken());
			
			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 s = Integer.parseInt(st.nextToken());
				int e = Integer.parseInt(st.nextToken());
				adjList[s].add(e);
				adjList[e].add(s);
			}
			
			isEnd = false;
			visited = new int[V+1];
			boolean endTest = false;
			for (int i = 1; i <= V; i++) {
				if(isEnd) {
					sb.append("NO\n");
					endTest = true;
					break;
				}
				if(visited[i] == 0) {
					solve(i, 1);
				}
			}
			if(!endTest) {
				sb.append("YES\n");
			}
			
		} // testcase
		
		System.out.println(sb.toString());
	} // main

	// visited에 0 이면 방문 x, 1팀, 2팀
	static boolean isEnd;
	static int[] visited;
	private static void solve(int head, int team) { 
		if(isEnd) {
			return;
		}
		
		visited[head] = team;
		for(int num : adjList[head]) {
			if (visited[head] == visited[num]) {
				isEnd = true;
				return;
			} else if(visited[num] == 0) {
				if(visited[head] == 1) {
					solve(num, 2);
				} else {
					solve(num, 1);
				}
			} 
		}
	} // solve
	
}

 

 

2. bfs

package Baekjoon;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ_1707_이분그래프_bfs {
	static List<Integer>[] adjList;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int K = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		for (int t = 0; t < K; t++) {
			st = new StringTokenizer(br.readLine());
			int V = Integer.parseInt(st.nextToken());
			int E = Integer.parseInt(st.nextToken());
			
			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 s = Integer.parseInt(st.nextToken());
				int e = Integer.parseInt(st.nextToken());
				adjList[s].add(e);
				adjList[e].add(s);
			}
			
			visited = new int[V+1];
			boolean endTest = false;
			for (int i = 1; i <= V; i++) {
				if(visited[i] == 0) {
					if(!bfs(i)) {
						endTest = true;
						sb.append("NO\n");
						break;
					}
				}
			}
			
			if(!endTest) {
				sb.append("YES\n");
			}
			
		} // testcase
		
		System.out.println(sb.toString());
	} // main

	// visited에 0 이면 방문 x, 1팀, 2팀
	static int[] visited;
	private static boolean bfs(int head) { 
		Queue<Integer> q = new LinkedList<>();
		q.offer(head);
		visited[head] = 1;
		
		int p;
		while(!q.isEmpty()) {
			p = q.poll();
			
			for(int num : adjList[p]) {
				if(visited[num] == 0) {
					q.offer(num);
					visited[num] = 3-visited[p];
				} else if(visited[num] == visited[p]) {
					return false;
				}
			}
			
		} // while
		
		return true;
	} // solve
	
}