백준 1707 java 이분그래프 (그래프)

문제, 입출력, 테스트케이스

이분그래프에 대한 정의를 이해 하지 못해서 한 1주일 정도는 그냥 바라본 문제다. 답지를 보기에는 골드4라는 티어 때문에 용납이 되지 않았고 금방 풀 수 있을 것 같아서 뚫어져라 쳐다 봤다. 결국 두색 칠하기 문제로 귀결되는 듯 보였다.

25단계 그래프와 순회 all solve!!

<문제 풀이/접근과정>
1. 인접한 두 수는 다른 색, 다른 숫자, 다른 그룹으로 짝지어 질 수 있는가
2. 그렇다면 조합으로는 안되나? => 조합으로는 시간 복잡도가 터질 수 있음
3. dfs 또는 bfs를 돌리며 색칠해 나가다가 인접한 정점이 같은 색깔 또는 같은 숫자인지를 보면 되겠구나
4. 간선이 연결되지 않은 정점들은 어떻게 처리하지?
5. 간선이 연결되지 않은 정점들은 또 dfs 또는 bfs를 돌리면서 집합을 두 집합으로 만들면 되겠구나! 1번 집합 2번 집합이 나오면 3번 집합/4번 집합으로 분리되는 경우에 3, 4를 1,2로 치환하면 되는 문제니까!
6. 소스코드의 dfs(0, j, j)에서 마지막 그룹의 숫자를 j로 넣은 이유가 바로 5번의 1/-1로 dfs돌리면서 짝짓는 것과 2/-2, 3/-3 ... n/-n으로 집합 짓는 행위는 결국 두 그룹으로 나눌 수 있냐 없냐와 동치여서 가능하다는 점을 미리 일러둔다.

<소스코드>

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

public class Main {
	static List<Integer>[] v;
	static int group[];
	static String answer;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int K = Integer.parseInt(br.readLine());
		StringTokenizer stz;
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < K; i++) {
			stz = new StringTokenizer(br.readLine());

			int V = Integer.parseInt(stz.nextToken());
			int E = Integer.parseInt(stz.nextToken());

			v = new List[V + 1];
			group = new int[V + 1];
			answer = "YES";
			for (int j = 0; j < V + 1; j++) {
				v[j] = new ArrayList<Integer>();
			}

			for (int j = 0; j < E; j++) {
				stz = new StringTokenizer(br.readLine());

				int from = Integer.parseInt(stz.nextToken());
				int to = Integer.parseInt(stz.nextToken());

				v[from].add(to);
				v[to].add(from);
			}
			for(int j = 1; j <= V; j++) {
				if(group[i] == 0)
				dfs(0, j, j);
			}
			
			sb.append(answer).append("\n");
			
		}
		sb.setLength(sb.length()-1);
		System.out.print(sb.toString());
	}

	private static void dfs(int prv, int cur, int curgroup) {

		for (int i = 0; i < v[cur].size(); i++) {
			if (group[v[cur].get(i)] == curgroup) { 
				answer = "NO";
				return;
			} else if (group[v[cur].get(i)] == 0) {
				group[v[cur].get(i)] = curgroup * -1;
				dfs(cur, v[cur].get(i), curgroup * -1);
			}
		}

	}
}