백준 1707: 이분 그래프

BFS를 사용해서 풀었다. check 벡터에 0은 방문되지 않은 곳 1은 집합1 2는 집합2로 나누어주고 각 정점에서 탐색을 해주면서 같은 집합으로 이동하는 경우를 발견하면 NO를 출력해주면 된다.

1이후에 2, 2 이후에 1 을 check 벡터에 넣어주기 위해 식을 맨처음 check_num변수를 더하고 모듈로하고 온 갖 썡쑈를해서 계속해서 틀렸습니다를 남발했는데 현재의 값인 x와 다음 값이 temp사이의 관계식을 이용해서 계산하니 정답이 맞았다...

BFS, DFS 뭐로 하든 상관 없겠다. 난 BFS가 더 맘에 든다. 정복해나가는 느낌이어서 

개인적으로 교훈은 내가 세운 식을 너무 믿으면 안될 것 같다. 내가 세운 복잡한 식은 틀리기 마련이다. 문제에서 주어진대로 점화식을 세울려고 노력하자. 

#include <iostream>
#include <vector>
#include <queue>
#include <string>
using namespace std;
int main()
{
    //입출력을 받음
    int t_case, vertex, edge, input_1, input_2;
    cin >> t_case;
    //t_case만큼 시도
    for (int i = 0; i < t_case; ++i)
    {
        string result = "YES";
        cin >> vertex >> edge;
        vector<int> check(20001, 0);
        vector<vector<int>> a(20001);
        queue<int> q;
        
        //간선 입력 받기
        for (int i = 0; i < edge; ++i)
        {
            cin >> input_1 >> input_2;
            a[input_1].push_back(input_2);
            a[input_2].push_back(input_1);
        }
        //bfs 활용해서 풀기
        for (int j = 1; j <= vertex; ++j)
        {
            if (check[j] == 0)
            {
                int check_num = 1;
                q.push(j);
                //첫 포인트 체크넘버 설정 by 1
                check[j] = check_num;
                while (!q.empty())
                {
                    int x = q.front(); q.pop();
                    //1과2 를 번갈아 가면서 넣어줌    
                    for (int i = 0; i < a[x].size(); ++i)
                    {
                        int temp = a[x][i];
                        //탐색되지 않은 곳이라면 탐색
                        if (check[temp] == 0)
                        {
                            check[temp] = (check[x] % 2) + 1; //2, 1
                            q.push(temp);
                        }
                        else if (check[temp] == check[x])
                        {
                            //탐색한 곳인데 그곳이 같은 집합에 속한 정점이면
                            result = "NO";
                        }
                    }
                }
            }        
        }
        cout << result << endl;
    }
    return 0;
}