[백준] 1707번 - 이분 그래프 판별

 

이 문제를 풀기 위해서는 이분 그래프를 알아야 한다. 위 그림은 간선이 여러개 있지만 모든 간선들은 빨간색 정점과 초록색 정점으로 이어져있다. 이렇게 모든 간선들이 다른 색의 정점으로 이어진 형태의 그래프가 이분 그래프이다.

BFS, DFS 두 방식 모두 풀 수 있는데 지금까지 BFS를 많이 사용해서 DFS를 사용해 봤다.

 

int main()
{
	cin >> cases;
	for (int i = 0; i < cases; i++)
	{
		int vertex, ganseon;
		cin >> vertex >> ganseon;
		adjacent.resize(vertex);
		visited.resize(vertex);

		for (int j = 0; j < ganseon; j++)
		{
			int n1, n2;
			cin >> n1 >> n2;
			adjacent[n1 - 1].push_back(n2 - 1);
			adjacent[n2 - 1].push_back(n1 - 1);
		}		

		for (int i = 0; i < vertex; i++)
		{
			if(!visited[i])
			dfs(i);
		}
        ...

 

main에서 입력을 받고 모든 정점들에 대하여 dfs를 돌린다. 

 

...
		bool isB = true;

		for (int i = 0; i < vertex; i++)
		{
			for (int j = 0; j < adjacent[i].size(); j++)
			{
				if (visited[i] == visited[adjacent[i][j]])				
					isB = false;									
			}
		}
		answer.push_back(isB);

		for (int i = 0; i < vertex; i++)
		{
			adjacent[i].clear();
		}
		visited.clear();
	}

 

이분 그래프를 판별하는 법은 정점을 돌면서 정점과 인접한 정점이 같은 색이라면 이분 그래프가 아니다. 테스트 케이스가 여러 개이기 때문에 판별을 완료하면 adjacent(인접 정점 저장하는 2차원 벡터)와 visited(방문 여부체크)를 clear한다.

 

void dfs(int start)
{
	if (!visited[start])
	{
		visited[start] = 1;
	}

	for (int i = 0; i < adjacent[start].size(); i++)
	{
		int next = adjacent[start][i];
		if (!visited[next])
		{
			if (visited[start] == 1)
				visited[next] = 2;
			else if (visited[start] == 2)
				visited[next] = 1;
			dfs(next);
		}
	}
}

 

dfs에서는 visited에 아직 방문을 안했다면 0, 색1을 1, 색2를 2로 저장한다. 처음 방문한다면 1로 저장하고 dfs를 돌면서 깊이 내려가서 이전 노드와 다른 색2로 저장한다. if(!visited[next]) 조건 안에 코드를 작성하지 않고 if(visited[next)return;을 사용해서 애를 많이 먹었다. 이렇게 하면 start 정점의 인접한 정점을 도는 for 루프가 중간에 끊겨 오류가 발생한다.