1707번

1707번 - 이분 그래프

이 문제를 풀때 스스로 이분 그래프의 특성을 구하고 문제를 풀어보려고 했다.

그러다 보니 처음에는 이분코드는 순환하면 안되는 성질이 있구나 라고 생각하고 문제를 풀었는데 계속 오류가 났다.

그래서 구글링해서 찾아보니 이분코드는 홀수개의 노드일 때만 순환이 안되고, 짝수개의 노드일 때는 순환이 되었다...

그래서 그 다음으로는 시작노드를 1이라고 하고 그 다음 방문하는 노드를 2로 해주는 방식으로 이분그래프를 찾았다.

처음 시작값은 모든 노드를 0으로 만들어주고 방문 할때마다 노드에 번호를 붙여주는 식으로 풀었다.

그러다가 자신의 노드 번호와 이웃의 노드 번호가 같을 경우 이분 그래프의 성질을 만족하지 않으므로 isbinary를 false로 만들어주었다.

그리고 혹시 연결 요소가 존재 할 수 있으니 모든 노드에 대해서 BFS, DFS 를 하기 위해 for문으로 구현했다.

그런식으로 처음에 BFS 코드를 짰고, 이를 기반으로 DFS 코드를 짰는데

DFS로 코드를 짤 때 나는 대부분의 변수를 전역변수로 두는데 vector 값들을 초기화하지 않아서 실수가 발생했다.

항상 변수를 꼼꼼히 체크하는 습관을 만들어야겠다.

<BFS 정답 코드>

#include<iostream>
#include<vector>
#include<queue>
#include<string.h>
using namespace std;
 
 
 
int main()
{
    int tc;
    cin >> tc;
 
    for (int t = 1; t <= tc; t++)
    {
        int N, M;
        vector<int> node[20001];
        int check[20001];
        bool isbinary = true;
        memset(check, 0, sizeof(check));
    
        cin >> N >> M;
 
        for (int i = 0; i < M; i++)
        {
            int a, b;
            cin >> a >> b;
            node[a].push_back(b);
            node[b].push_back(a);
        }
 
        
 
        for (int i = 1; i <= N; i++)
        {
            if (check[i]==0 && isbinary)
            {
                queue<int> q;
                q.push(i);
                check[i] = 1;
 
                while (!q.empty() && isbinary)
                {
                    int now = q.front();
                    q.pop();
 
                    for (int j = 0; j < node[now].size(); j++)
                    {
                        int next = node[now][j];
 
                        if (check[next]==0)
                        {
                            check[next] = 3-check[now];
                            q.push(next);
                        }
                        else if (check[next] != 0 && check[now]==check[next])
                        {
                            isbinary = false;
                            break;
                        }
                    }
                }
            }
        }
 
        if (isbinary)
        {
            cout << "YES" << endl;
        }
        else
        {
            cout << "NO" << endl;
        }
    }
 
    return 0;
}

<DFS 정답 코드>

#include<iostream>
#include<vector>
#include<queue>
#include<string.h>
using namespace std;
int N, M;
vector<int> node[20001];
int check[20001];
bool isbinary;
 
void dfs(int start)
{
    if (isbinary)
    {
        for (int i = 0; i < node[start].size(); i++)
        {
            int next = node[start][i];
 
            if (check[next] == 0)
            {
                check[next] = 3 - check[start];
                dfs(next);
            }
            else if (check[next] != 0 && check[next] == check[start])
            {
                isbinary = false;
                break;
            }
        }
    }
 
    return;
}
 
int main()
{
    int tc;
    cin >> tc;
 
    for (int t = 1; t <= tc; t++)
    {
        isbinary = true;
        memset(check, 0, sizeof(check));
    
        for (int i = 1; i <= N; i++)
        {
            node[i].clear();
        }
        cin >> N >> M;
 
        for (int i = 0; i < M; i++)
        {
            int a, b;
            cin >> a >> b;
            node[a].push_back(b);
            node[b].push_back(a);
        }
 
        for (int i = 1; i <= N; i++)
        {
            if (check[i] == 0 && isbinary)
            {
                check[i] = 1;
                dfs(i);
            }
        }
 
 
        if (isbinary)
        {
            cout << "YES" << endl;
        }
        else
        {
            cout << "NO" << endl;
        }
    }
 
    return 0;
}