[C++] 백준 1707번 이분 그래프

그래프 탐색 문제.

처음에 진짜 말도 안되는 방법으로 구현했다가 틀렸다. (아무 생각없이 풀어버렸다.)

근데 또 예제들은 잘 나와서 뭐가 틀렸는지 몰랐는데 반례 게시판에 나와있는 반례를 통해 해결했다.

이번에 대회에 이분 그래프 문제가 나왔었는데,(사실 이분 그래프보다는 심화적인 내용이였다. 당연히 못풀었음ㅠ)

이분 그래프 문제는 유명한 문제 같아서 이번에 풀어봤다.

 

문제풀이

문제내용에 따르면 그래프에서 인접하지 않은 정점들끼리 집합을 나눌 수 있는 그래프인지 여부를 확인하면 된다.

그래프에서 정점에 색을 칠하는데, 인접한 정점끼리는 다른 색을 가지게 되면 해당 그래프를 이분그래프라고 할 수 있다.

 

나는 이 문제를 내가 빨간색, 파란색 붓만 가지고있고, 색칠되지 않은 정점에 빨간색 붓을 칠하면서 시작하고 해당 정점과 인접한 곳에는 파란색으로, 다시 파란색 정점과 인접한 곳에는 빨간색으로, 이렇게 칠해나간다고 생각하고 문제를 풀었다.

 

처음에는 이렇게 생각하지 않았는데, https://www.acmicpc.net/board/view/34859 게시판에서 알려준 반례를 통해 위처럼 다시 생각해서 풀게 되었다.

1 4 3 1 4 2 3 3 4

위 반례의 정답은 YES이다. 하지만 정답 전에 내 코드는 NO를 출력했다.

정답 전에 내 코드는 인접한 곳들에 모두 다른색을 칠하고, 색이 칠해지지 않은 곳에만 색을 칠하는 형식으로 만들었다.

그러나, 이런 식으로 로직을 짜면 다음과 같은 순서로 진행되어서 위 코드가 NO를 출력한다.

1. 1 색깔 없음. 1 -> 4 / 1 : 빨간색, 4 : 파란색
2. 2 색깔 없음. 2 -> 3 / 2 : 빨간색, 3 : 파란색
3. 3, 4 둘 다 색깔 있으므로 PASS
4. 집합은 1, 2 / 3, 4인데 3과 4가 인접하므로 NO

이런 식으로 짜면 오답이다. 따라서 다른 방법을 선택했다.

DFS와 비슷한 방식으로, 색이 없는 곳에는 빨간색으로 시작한 후에, 인접한 곳에 파란색으로 칠하고 다시 그 인접한 곳에서 색칠하는 방식을 선택했다.

말로만 들으면 위와 비슷해보이지만, 이 방법은 아래와 같은 순서로 진행된다.

1. 1 색깔 없음. 1 -> 4 / 1 : 빨간색, 4 : 파란색
2. 4 파란색. 4 -> 3 / 3 : 빨간색
3. 3 빨간색. 3-> 2 / 2 : 파란색
4. 집합은 1, 3 / 2, 4 이므로 YES

 

DFS처럼 해당 정점을 칠하고, 주변 정점 중 색이 없는 정점에 색을 칠해주는 방식으로 만들었다.

 

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

int tc;
int vertexCnt, edgeCnt;
vector<int> adjList[20001];
int color[20001];
bool ans;

사용한 STL과 변수

 

• tc : 테스트 케이스의 개수
• vertexCnt, edgeCnt : 각 테스트 케이스마다 입력받는 정점, 간선의 개수
• adjList 벡터 : 각 정점마다 몇 번의 정점과 연결되어 있는지 기록하는 벡터
• color 배열 : 각 정점이 무슨 색인지 기록하는 배열 ( 1과 2)
• ans : 현재 그래프가 이분 그래프인지 확인하는 변수. true라면 가능.

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

	cin >> tc;

	while (tc--) {
		for (int i = 1; i <= vertexCnt; i++) {
			adjList[i].clear();
			color[i] = 0;
		}
		ans = true;

		cin >> vertexCnt >> edgeCnt;

		int num1, num2;
		for (int i = 1; i <= edgeCnt; i++) {
			cin >> num1 >> num2;
			adjList[num1].push_back(num2);
			adjList[num2].push_back(num1);
		}

		for (int i = 1; i <= vertexCnt; i++) {
			if (color[i] == 0) {
				coloring(i, 1);
			}
		}

		for (int i = 1; i <= vertexCnt; i++) {
			if (!checkColor(i)) {
				ans = false;
				break;
			}
		}

		if (ans) {
			cout << "YES\n";
		}
		else {
			cout << "NO\n";
		}
	}

	return 0;
}

메인함수

 

처음에 테스트 케이스를 입력받는다.

후에 각 테스트 케이스마다 인접한 정점들을 초기화(adjList[i].clear) 해주고 색도 초기화 해준다.

그리고 ans는 초기에 true로 초기화 해준다.

 

정점의 개수와 간선의 개수를 나중에 입력받는데, 초기화는 그 이전에 입력했던 정점의 개수와 간선의 개수를 토대로 초기화하기 때문이다.

 

그리고 연결된 두 정점의 정보를 입력받고 adjList 벡터에 저장해둔다.

 

연결된 정점의 정보를 토대로 1번부터 색칠되지 않은 정점에 색칠을 한다.

coloring() 현재 정점을 색칠한 후에, 인접한 정점들에는 현재 정점에 칠한 색과 반대되는 색으로 색칠하는 메서드이다. 메인함수에서 호출될 때는 1번으로 색칠하도록 무조건 시작하도록 만들었다.

void coloring(int num, int colorNum) {
	color[num] = colorNum;

	int nxtColorNum = (colorNum == 1) ? 2 : 1;

	for (int adjNum : adjList[num]) {
		if (color[adjNum] == 0) {
			coloring(adjNum, nxtColorNum);
		}
	}
}

색을 칠하는 메서드는 다음과 같은 구조이다.

 

현재 정점에 색을 칠한 후에, 다음 정점에 무슨 색을 칠해야 하는지 nxtColorNum 변수에 기록해둔다.

그리고 인접한 정점들 중 색이 칠해지지 않은 곳에 현재 정점과 반대되는 색으로 칠해주고 해당 정점번호로 coloring 메서드를 호출한다.

 

색칠이 끝나면, 모든 정점에 대해 검사한다. 현재 정점과 인접한 정점이 같은 색이 아닌지를 확인한다.

checkColor() 메서드가 그 역할을 해주고, 현재 정점에서 모든 인접한 정점과 다른 색일 경우 true, 같은 색이 하나라도 있을 경우 false를 return한다.

 

bool checkColor(int num) {
	for (int adjNum : adjList[num]) {
		if (color[adjNum] == color[num]) {
			return false;
		}
	}
	return true;
}

위와 같은 구조로 이루어져 있다. 어려운 부분이 없으므로 설명은 생략하겠다.

 

만일 하나라도 false가 된다면 해당 그래프는 이분 그래프가 아니다. ans를 false로 바꾸고 break를 걸어준다.

 

그리고 ans에 따라서 YES 또는 NO를 출력해주면 된다.

 

그래프 탐색 중 어려운 것 같으면서도 막상 제대로 풀어보니 크게 어려운 것 같지는 않다.

 

GitHub - kimyunseok/cpp: my study-record

코드 전문은 위에서 확인이 가능하다.