[백준 13265] 색칠하기 (C++)

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

문제

---

어린 토니킴은 색칠공부를 좋아한다.

토니킴은 먼저 여러 동그라미와 동그라미 두 개를 연결하는 직선들 만으로 그림을 그리고 (모든 동그라미들 사이에 직선이 있을 필요는 없다), 연결된 두 동그라미는 서로 색이 다르게 되도록 색을 칠하고자 한다.

이 그림을 색칠하는데 필요한 최소의 색의 개수를 구하는 문제는 어렵기 때문에 토니킴은 2 가지 색상으로 색칠이 가능한지의 여부만을 알고 싶어한다.

동그라미들의 번호와 동그라미들이 서로 연결된 직선에 대한 정보가 주어졌을 때, 이 동그라미들이 2 가지 색상으로 색칠이 가능한지 알아내자.

 

입력

---

입력의 첫 줄에는 테스트 케이스의 개수 T 가 주어진다.

그 다음 줄부터 각 테스트 케이스에 대해 동그라미의 개수 n(1 ≤ n ≤ 1000)과 직선들의 개수 m(1 ≤ m ≤ 100,000)이 주어지고, 그 다음 줄부터 m 줄에 걸쳐 동그라미들이 연결된 직선에 대한 정보가 주어진다. (x y)로 주어지면 동그라미 x와 동그라미 y가 직선으로 서로 연결되었다는 의미이다. 동그라미들의 번호는 1 부터 n 까지이다.

 

출력

---

각 테스트 케이스에 대해서 possible 이나 impossible 을 출력한다. 2 가지 색상으로 색칠이 가능하면 possible. 불가능하면 impossible 이다.

 

문제 풀이

---

그래프 탐색 문제.

 

주어진 그래프가 이분 그래프인지 확인해주면 된다. bfs나 dfs로 그래프를 탐색하며 해당 동그라미를 두 가지 색깔중 한 색깔로 채워준다. 첫 탐색을 시작할 때 아무 색깔으로 채운 후, bfs나 dfs로 탐색하며 연결된 다음 노드를 이와 다른 색깔로 채워주면 된다.

 

아래는 코드.

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

int N, M;
vector<int>* edges;
char* colors;
bool* isVisited;
bool isPossible;

queue<int> bfsQueue;

void bfs(int startNum)
{
	colors[startNum] = 'R';
	isVisited[startNum] = true;
	bfsQueue.push(startNum);
	while (!bfsQueue.empty())
	{
		int current = bfsQueue.front();
		for (int i = 0; i < edges[current].size(); i++)
		{
			int next = edges[current].at(i);
			if (isVisited[next] == false)
			{
				bfsQueue.push(next);
				isVisited[next] = true;
				if (colors[current] == 'R')
				{
					colors[next] = 'B';
				}
				else
				{
					colors[next] = 'R';
				}
			}
			else
			{
				if (colors[current] == colors[next])
				{
					isPossible = false;
				}
			}
		}
		bfsQueue.pop();
	}
}

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int T;
	cin >> T;
	for (int t = 0; t < T; t++)
	{
		cin >> N >> M;
		isPossible = true;
		int a, b;
		edges = new vector<int>[N + 1];
		colors = new char[N + 1];
		isVisited = new bool[N + 1];
		for (int i = 0; i < N + 1; i++)
		{
			isVisited[i] = false;
		}
		for (int i = 0; i < M; i++)
		{
			cin >> a >> b;
			edges[a].push_back(b);
			edges[b].push_back(a);
		}
		for (int i = 1; i <= N; i++)
		{
			if (isVisited[i] == false)
			{
				bfs(i);
			}
		}
		if (isPossible == false)
		{
			cout << "impossible" << "\n";
		}
		else
		{
			cout << "possible" << "\n";
		}
	}
	return 0;
}