[백준/c++] 1707번: 이분 그래프

문제 링크 - https://www.acmicpc.net/problem/1707

🌱 문제

🌱 풀이

• 넘나 헤맸던 문제였다.
• 주의할점은, 문제에서 주어진 그래프가 모두 연결되어있다는 보장이 없음에 주의해야한다!! 즉, 안이어진 그래프도 고려해야한다. (이런건 문제에 써있어야 하는거 아닌가 ... ㅠㅠ)

풀이

• BFS를 이용하여 풀었다. bool로 선언하여 이분그래프가 아님을 알게되면 바로 return false한다. (끝까지 다돌면 true인것)
  int color[20001] : 0:아직 방문하지 않음, 1: 1번색깔, 2:2번색깔
  bool flag : 대답(yes,no)를 출력하기 위한 bool형 변수

1. 각 테스트별로 정점 및 간선정보를 입력받는다.
2. for문을 통해 i번째 정점이 방문하지 않았으면 bfs를 돌린다. 이때 color==0 이면 방문하지 않은것이다.
3. bfs에서 첫 정점은 1번 color라 가정했다.bfs를 돌면서 인접한 정점의 색을 정해준다.
   (이때 일반 bfs에서는 방문체크를 하고, 방문 안한 정점에 대해서만 다음 처리를 했었다. 이번 이분그래프 문제에서는 다음 정점이 방문했던 정점이라도 현재 정점과 다음 정점의 color가 같은지 다른지 확인해줘야 하므로 전부 봐줘야 한다.)
   3-1. 다음 정점이 방문 안한 정점이면, 현재 정점의 color와 다른 color로 지정해주고 queue에 삽입한다.
   3-2. 다음 정점이 방문했던 정점이라면, 현재 정점의 color와 같은지 확인한다. 같으면 이분그래프 조건을 불만족 하는것이므로 return false한다.
4. main문에서 각 정점별로 bfs를 돌다가 bfs가 하나라도 false이면 flag=false로 지정한다. 그 테스트케이스는 NO가 답이니까 break로 그냥 나온다.
5. flag를 확인하고 결과를 출력한다.
6. *주의 - 한 테스트케이스가 끝나면 color배열 초기화 하고, vector배열 clear 해줘야 한다.

테스트케이스 문제 시 기억할점

• 테스트 케이스 문제는 배열을 초기화하거나 벡터를 clear하는 경우가 자주 있다.

• 헤더파일 및 문법을 기억해놓자.

• 배열 초기화 - 'cstring' 헤더 선언
  ex)memset(color, 0, sizeof(color)); // color 배열 초기화

• vector 배열 초기화

for (int i = 1; i <= v; i++) { //vector 배열 clear
            vec[i].clear();
 }

🌱 코드

// 1707: 이분그래프
/*
테케 K
정점 V
간선 E

2<=K<=5
1<=v<=20,000
1<=E<=200,000

*/

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

int k, v, e;
vector<int> vec[20001];
queue<int> q;
int color[20001];//집합-> 색깔(1,2)를 나타냄
bool flag; //대답 출력시에 사용

bool bfs(int x){
    queue<int> q;
    q.push(x);
    color[x] = 1; //처음정점(1번정점)은 1번색깔이라고 가정  

    while (!q.empty()){
        int y = q.front();
        q.pop();

        for (int i = 0; i < vec[y].size(); i++) {
            int z = vec[y][i];

             if (color[z] == 0){
                color[z] = (color[y] == 1) ? 2 : 1;
                q.push(z);

            }
            else if (color[y] == color[z]){
              return false;
            }
        }
    }

    return true;
}

int main()
{
    cin >> k;
    for (int i = 0; i < k; i++){
        int v, e;
        cin >> v >> e;

        for (int j = 0; j < e; j++){
            int u, v;
            cin >> u >> v;
            vec[u].push_back(v);
            vec[v].push_back(u);
        }

        flag=true;
        for(int i=1; i<=v; i++){
            if(color[i]==0){
                if(bfs(i)==false){
                    flag=false;
                    break;
                }
            }
        }
        
        if(flag==true)
        cout<<"YES"<<"\n";
        else
        cout<<"NO"<<"\n";

        memset(color, 0, sizeof(color)); // color 배열 초기화
        for (int i = 1; i <= v; i++) { //vector 배열 clear
            vec[i].clear();

        }
    }
}