bfs를 이용하는 문제로, 문제 자체는 골드4인 것에 비해 어렵지 않은 난이도를 가진 문제이다.
하지만 내 코딩 실력은 상상을 초월했다.
사실 기본 로직 자체는 처음부터 맞게 설계했지만 일부 처리에 문제가 있어 틀렸습니다를 도배하였다. 저 중 8개는 사실상 같은 코드임.
이분 그래프는 인접한 노드끼리 서로 다른 그룹으로 분류할 수 있는 그래프이다. 따라서 자신과 인접한 노드가 서로 다른 그룹인지만 체크하면 된다.
자신과 인접한 노드가 이전에 방문한 적 없는 노드라면 특정 그룹에 분류돼있지 않은 상태이니 방문체크를 해주고 그룹을 지정해주면 되고, 방문한 적 있는 노드라면 자신과 같은 그룹인지 체크하면 된다. 따라서 일반적인 bfs와 큰 차이가 없는 코드를 가진다.
두 가지 요소를 간과하였다.
첫째는 여러 개의 테스트케이스를 가지는 만큼 변수들의 초기화에 신경써야 한다는 것. 필자는 bfs를 함수로 분리하였고, 사용되는 큐나 배열 등을 매개변수로 전달하지 않고 전역변수로 두었기 때문에 각 케이스에 대한 처리가 끝나고 전역변수들의 초기화가 매우 중요했으나, 일부 변수의 초기화를 정상적으로 처리하지 않았다.
둘째, 불완전 그래프에 대한 것을 간과하였다. 이것이 헤맨 주 원인인데, 애꿎은 로직만 들여다보고 그룹 넘버 바꿔보고 이상한 짓을 다 하였지만 반례를 찾는 것이 더 중요하였다. 문제에서 주어지는 모든 정점이 이어진 완전 그래프라는 조건이 없었는데 필자는 완전 그래프일 것이라고 믿은 것이다.
첫 번째 정점에 대해서만 bfs를 실행했기 때문에 첫 번째 정점에 이어지지 않은 정점들에 대한 이분 그래프 탐색이 이루어지지 않아 자꾸 문제를 틀린 것이다. 따라서 그래프 내 모든 정점에 대해 방문 처리가 된 정점인지 확인하고 방문 처리가 안 된 정점이라면 해당 정점에 대해 추가적인 이분 그래프 판별을 해주어 정답 처리가 될 수 있었다.
이 모든 내용을 바탕으로 작성된 최종 코드는 아래와 같다.
#include <iostream>
#include <vector>
#include <queue>
int v, e;
std::queue<int> q;
std::vector<int> graph[20001];
int visit[20001];
int group[20001];
bool bfs(){
while(!q.empty()){
int cur = q.front();
q.pop();
for(auto adj : graph[cur]){
if(!visit[adj]){
q.push(adj);
visit[adj] = 1;
group[adj] = group[cur] * -1;
}
else if(group[cur] == group[adj]){
return false;
}
}
}
return true;
}
void reset(){
for(int index = 0; index <= v; index++){
visit[index] = 0;
group[index] = 0;
graph[index].clear();
}
while(!q.empty()){
q.pop();
}
}
int main(){
int cases;
scanf("%d", &cases);
for(int count = 0; count < cases; count++){
scanf("%d %d", &v, &e);
int vert1, vert2;
for(int edgeCount = 0; edgeCount < e; edgeCount++){
scanf("%d %d", &vert1, &vert2);
graph[vert1].push_back(vert2);
graph[vert2].push_back(vert1);
}
bool bipartite = true;
for(int index = 1; index <= v; index++){ // 불완전 그래프를 위한 모든 정점 탐색
if(!visit[index]){
q.push(index);
visit[index] = 1;
group[index] = 1;
}
if(!bfs()){
bipartite = false;
break;
}
}
(bipartite) ? printf("YES\n") : printf("NO\n");
reset();
}
}