궤도
[백준] 1707번 : 이분 그래프 본문
문제
풀이
이 문제는 그냥 구글에 이분그래프라고 검색하고 나온 이미지를 보는 것만으로도 한 절반정도는 풀리는 문제이다.
위키백과 이미지를 가져왔다. 그래프의 정점을 빨간색과 초록색으로 칠한 것을 볼 수 있을 것이다.
이분그래프는 인접한 두 정점을 다른색으로 칠한다고 가정할 때 오직 두가지의 색을 사용해서 모든 정점을 칠할 수 있는 그래프이다.
자료구조때 배웠던가...컴퓨터 알고리즘때 배웠던가...암튼 배웠었다.
아이디어는 간단한 이 문제가 정답 비율 20%대인 이유는 간과하기 쉬운 조건 하나와 메모리 초과 그리고 입력 초기화 떄문 아닐까싶다.
먼저 간과하기 쉬운 조건하나를 말해보도록 하겠다.
바로 모든 정점이 연결됐을거란 보장이 없다는 것이다.
이 그림처럼 다른 정점과 연결되지 않은 정점이 있을 수 있다.
만약 다른 정점과 다른 그룹으로 분리된 정점이 저런 형태라면 이건 이분그래프가 될 수 없다.
그니까 큐가 비어있더라도 방문하지 않은 정점이 있는지 확인해야 한다.
다음으로 메모리 초과에 대해 말해보겠다.
처음에 모든 그래프의 간선 정보를 2차원 배열에 저장했다가 메모리 초과를 받았다.
입력조건을 보면 정점은 최대 20,000개까지 들어오고 간선은 최대 200,000개까지 들어온다.
그럼 최대 입력이 들어와도 정점당 평균 10개의 간선이 있단 건데
이걸 저장하기 위해 20,000x20,000크기의 배열을 사용하는건 비효율적이며 당연히 저 크기는 메모리 초과가 발생할 것이다.
그래서 리스트 개념을 생각했다.
예제 입력 1의 2번째 테스트 케이스에 대해 간선 리스트를 만든 것이다.
그럼 이걸 실제로 어떻게 구현할까? 2차원 벡터를 사용하면 된다.
2차원 벡터는 각 행마다 열의 크기를 자유롭게 설정할 수 있기 때문이다.
소스코드
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
vector<vector<int>> graph; //배열에 넣으면 메모리 초과라 벡터 사용
vector<int> color; //0: 방문 하지 않음, 1: 1로 색칠, 2: 2로 색칠
int V, E;
int getColor(int color) { //무슨 색으로 칠해야 하는지 알려주는 함수
if (color == 1)
return 2;
return 1;
}
void bfs() {
int cur = 1; //1번 정점부터 시작
queue<int> q;
color[cur] = 1;
q.push(cur);
while (!q.empty()) {
cur = q.front();
q.pop();
for (int i = 0; i < graph[cur].size(); i++) {
if (color[graph[cur][i]] == 0) { //방문한 적 없는 정점이라면 color[cur]과 다른 색으로 칠해서 방문 표시
color[graph[cur][i]] = getColor(color[cur]);
q.push(graph[cur][i]);
} else if (color[graph[cur][i]] == color[cur]) { //연결된 정점끼리 색이 같다면 이분 그래프일 수 없음
cout << "NO\n";
return;
}
}
if (q.empty()) { //어떤 정점과도 연결되지 않은 정점이 있을 수 있음
for (int i = 1; i <= V; i++) {
if (color[i] == 0) {
color[i] = 1;
q.push(i);
break;
}
}
}
}
cout << "YES\n";
return;
}
int main() {
int K, first, second;
cin >> K;
for (int i = 0; i < K; i++) {
cin >> V >> E;
graph.assign((V + 1), vector<int>(0)); //(V+1)x(0)의 크기 할당
color.assign((V + 1), 0);
for (int j = 0; j < E; j++) { //graph[source].push_back(dest)
cin >> first >> second;
graph[first].push_back(second);
graph[second].push_back(first);
}
bfs();
graph.clear(); //2차원 벡터 초기화
color.clear(); //1차원 벡터 초기화
}
}전체 소스코드다.
vector<vector<int>> graph; //배열에 넣으면 메모리 초과라 벡터 사용
vector<int> color; //0: 방문 하지 않음, 1: 1로 색칠, 2: 2로 색칠
int V, E;간선 정보를 저장할 2차원 벡터 graph와 방문여부와 정점의 색을 저장할 벡터 color이다.
color의 값이 0이면 방문을 하지 않은 것이고, 1이면 1로 색칠한 것이며 2면 2로 색칠한 것이다.
cin >> K;
for (int i = 0; i < K; i++) {
cin >> V >> E;
graph.assign((V + 1), vector<int>(0)); //(V+1)x(0)의 크기 할당
color.assign((V + 1), 0);
for (int j = 0; j < E; j++) { //graph[source].push_back(dest)
cin >> first >> second;
graph[first].push_back(second);
graph[second].push_back(first);
}
bfs();
graph.clear(); //2차원 벡터 초기화
color.clear(); //1차원 벡터 초기화
}다음으로 입력 받는 부분이다.
각 테스트 케이스에 대해 정점의 개수 V와 간선의 개수 E를 입력받는다.
그리고 벡터에 내장된 assign 함수를 이용해 (V+1) 크기의 행과 0 크기의 열을 할당한다.
각 간선이 입력될 때마다 graph 벡터에 넣어준다. 만약 1 2가 입력으로 들어왔다면 정점 1과 2가 연결됐다는 것이다.
그래서 graph[1]에 2를 넣어주고 graph[2]에도 1을 넣어준다.
그리고 중요한건데 각 테스트 케이스의 이분그래프 여부를 확인하고 난 뒤 graph 벡터와 color 벡터를 초기화 해야 한다.
void bfs() {
int cur = 1; //1번 정점부터 시작
queue<int> q;
color[cur] = 1;
q.push(cur);
while (!q.empty()) {
cur = q.front();
q.pop();
for (int i = 0; i < graph[cur].size(); i++) {
if (color[graph[cur][i]] == 0) { //방문한 적 없는 정점이라면 color[cur]과 다른 색으로 칠해서 방문 표시
color[graph[cur][i]] = getColor(color[cur]);
q.push(graph[cur][i]);
} else if (color[graph[cur][i]] == color[cur]) { //연결된 정점끼리 색이 같다면 이분 그래프일 수 없음
cout << "NO\n";
return;
}
}
if (q.empty()) { //어떤 정점과도 연결되지 않은 정점이 있을 수 있음
for (int i = 1; i <= V; i++) {
if (color[i] == 0) {
color[i] = 1;
q.push(i);
break;
}
}
}
}
cout << "YES\n";
return;
}이분 그래프를 판별하는 bfs 함수이다.
int cur = 1; //1번 정점부터 시작
queue<int> q;
color[cur] = 1;
q.push(cur);먼저 1번 정점부터 시작한다. 어차피 모든 정점을 방문하게 될 것이기 때문에 1번부터 시작한다.
cur = q.front();
q.pop();
for (int i = 0; i < graph[cur].size(); i++) {
if (color[graph[cur][i]] == 0) { //방문한 적 없는 정점이라면 color[cur]과 다른 색으로 칠해서 방문 표시
color[graph[cur][i]] = getColor(color[cur]);
q.push(graph[cur][i]);
} else if (color[graph[cur][i]] == color[cur]) { //연결된 정점끼리 색이 같다면 이분 그래프일 수 없음
cout << "NO\n";
return;
}
}각 정점과 연결된 정점을 담은 리스트를 확인한다.
방문하지 않은 정점이라면 원래의 정점과 다른 색으로 칠한다. 근데 원래의 정점과 같은 색으로 이미 칠해진 정점이 발견될 수도 있다.
그렇다면 이분 그래프가 될 수 없으므로 NO를 출력하고 함수를 종료한다.
if (q.empty()) { //어떤 정점과도 연결되지 않은 정점이 있을 수 있음
for (int i = 1; i <= V; i++) {
if (color[i] == 0) {
color[i] = 1;
q.push(i);
break;
}
}
}이 과정이후 큐가 비어있는 상태가 될 수도 있다. 하지만 지금까지 탐색한 정점들과 연결되지 않아 탐색하지 못한 정점이 있을 수도 있기 때문에 그런 정점을 찾아서 큐에 넣어준다. 이 정점이 새로운 start 정점이 된다고 생각해도 된다.
cout << "YES\n";
return;while문을 문제없이 빠져나왔다면 이분그래프라는 것이다.
