알고리즘 :: 백준 :: DFS :: 1707:: 이분 그래프

문제

문제접근

이 문제에 대한 상세 설명은 알고리즘 :: 백준 :: DFS :: 1707:: 이분 그래프 (velog.io)에 있습니다. 이번에는 같은 문제를 조금 더 효율적으로 풀어보겠습니다.

문제 이해

• 문제 조건에는 나와있지 않지만, 본 문제의 이분그래프는 무방향 그래프입니다.
• 이분그래프의 특징에 의해 임의의 정점에서 다른 정점으로 간선을 타고 이동할 때 도착 정점은 시작 정점과 반대 그룹에 넣어줍니다. (A → B → A → B...)
• 만일 임의의 정점에서 다른 정점으로 이동할 때, 해당 정점이 이미 방문한 점이며 같은 그룹이라면 이분그래프 조건을 위배하게 됩니다.

풀이과정

• 임의의 정점을 시점으로 모든 점을 탐색하기 위해서는 DFS 또는 BFS를 사용해야 함을 알 수 있습니다.
  이 문제는 둘 중 무엇을 사용해도 상관없습니다.
• 제게는 임의의 정점을 기준으로 간선을 따라 깊게 이동하는 그림이 조금 더 익숙해서 DFS를 사용했습니다.
• 0을 방문하지 않은 점, 1을 그룹 A, 2를 그룹 B라고 가정하고 state[] 배열을 선언합니다.
• 임의의 정점의 state가 x일 때 다음 정점의 state는 3-x 입니다. (1 → 2, 2 → 1)
• 이때 연결된 다음 정점이 이미 방문한 점이고 state가 같디면 이분그래프가 아닌 것을 확인할 수 있습니다.

코드

#include <iostream>
#include <vector>
using namespace std;

bool ans;
int K, V, E, state[20001];
vector<int> graph[20001];

void dfs(int cv, int s) {
	state[cv] = s;
	for (int nv : graph[cv]) {
		// 방문하지 않은 정점에 대해 반대 그룹 표시
		if (!state[nv]) dfs(nv, 3 - s);
		// 방문된 정점에 대해 같은 그룹 여부 확인
		if (state[nv] == state[cv]) { ans = true; break; }
	}
}

void solve() {
    // 모든 정점에 대해 dfs를 수행함.
	for (int i = 1; i <= V; ++i) {
		if (!state[i]) dfs(i, 1);
		if (ans) break;	// 이분그래프가 아닌 경우
	}
}

void clear() {
	ans = false;
	fill(state, state + V + 1, false);
	for (int i = 1; i <= V; ++i) graph[i].clear();
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> K;
	while (K--){
		cin >> V >> E;
		int sv, ev;
		for (int i = 0; i < E; ++i) {
			cin >> sv >> ev;
            // 무방향 그래프
			graph[sv].push_back(ev);
			graph[ev].push_back(sv);
		}
		solve();
		ans ? cout << "NO\n" : cout << "YES\n";
		clear();	// 다음 loop를 위한 초기화 과정
	}
}

결과