[백준 1707] 이분 그래프 (C++, Java)

문제 링크: https://www.acmicpc.net/problem/1707

1707번: 이분 그래프

1. 주의할 점

- BFS,DFS 모두 가능한 문제지만, BFS로 접근하면 시간이 더 적게 소요된다.

- 입력받은 정점과 간선을 통해서 1개 이상의 그래프가 생성될 수 있다(따라서 모든 Node에 대해 방문했는지 검사가 필요하다)

 

2. 구현

- Node 1번부터 N번까지 검사를 하면서 방문을 하지 않았다면 Queue에 입력후 BFS를 시작한다

- BFS를 사용하는 이유로는 현재 Node를 기점으로 나와 연결된 다른 Node에는 다른색을 칠하면 된다.

- 이분 그래프를 생성할 수 없는 경우로는, 나와 연결된 다른 Node에 나와 같은 색이 이미 칠해져 있는 경우다.

 

[C++]

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> v[20001];
int visit[20001];
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int test, node, edge, start, end;
	cin >> test;
	for (int t = 0; t < test; t++) {
		cin >> node >> edge;
		for (int i = 1; i <= node; i++) {
			v[i].clear();
			visit[i] = -1;
		}
		for (int i = 0; i < edge; i++) {
			cin >> start >> end;
			v[start].push_back(end);
			v[end].push_back(start);
		}
		bool avail = true;
		for (int k = 1; k <= node; k++) {
			if (visit[k] != -1) continue;
			queue<int> q;
			q.push(k);
			visit[k] = k;
			while (!q.empty()) {
				int cidx = q.front();
				q.pop();
				for (int i = 0; i < v[cidx].size(); i++) {
					int next = v[cidx][i];
					if (visit[next] == -1) {		//아직 방문 안한 경우
						visit[next] = 3 - visit[cidx];
						q.push(next);
					}
					else if (visit[next] == visit[cidx]) {		//나랑 같은 집합인데 한번 더 연결하려는 경우 -> 이분그래프 실패
						avail = false;
						break;
					}
				}
				if (!avail) break;
			}
			if (!avail) break;
		}
		if (avail) cout << "YES" << '\n';
		else cout << "NO" << '\n';
	}
	system("pause");
	return 0;
}

 

[Java]

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 Main {
	static class Info {
		int idx, color;

		public Info(int idx, int color) {
			this.idx = idx;
			this.color = color;
		}
	}

	static int node, edge, v[];
	static List<Integer> li[];

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int test = Integer.parseInt(br.readLine());
		for (int t = 0; t < test; t++) {
			String str = br.readLine();
			StringTokenizer st = new StringTokenizer(str);
			node = Integer.parseInt(st.nextToken());
			edge = Integer.parseInt(st.nextToken());

			// 초기화
			v = new int[node + 1];
			li = new List[node + 1];
			for (int i = 1; i <= node; i++)
				li[i] = new ArrayList<Integer>();

			for (int i = 0; i < edge; i++) {
				str = br.readLine();
				st = new StringTokenizer(str);
				int s = Integer.parseInt(st.nextToken());
				int e = Integer.parseInt(st.nextToken());
				li[s].add(e);
				li[e].add(s);
			}
			boolean avail = true;
			for (int k = 1; k <= node; k++) {
				if(v[k]!=0) continue;
				Queue<Info> q = new LinkedList<>();
				q.offer(new Info(k, -1));
				v[k] = -1;
				Info ii;

				while (!q.isEmpty()) {
					ii = q.poll();
					int cidx = ii.idx;
					int cc = ii.color;
					for (int i = 0; i < li[cidx].size(); i++) {
						int next = li[cidx].get(i);
						if (v[next] == cc) {
							avail = false;
							break;
						} else if (v[next] == 0) {
							v[next] = -cc;
							q.offer(new Info(next, -cc));
						}
					}
				}
				if(!avail) break;
			}
			System.out.println(avail == true ? "YES" : "NO");
		}
	}
}