[BFS] 백준 1707번 이분 그래프(C++)

https://www.acmicpc.net/problem/1707

 

장난 아니다.

이게 무슨 문제인것인가...

예시를 봐도 이해가 안간다...

 

[DFS,BFS] 백준 1260번 BFS와 DFS(C++)

앞선 dfs와 bfs를 꼭 풀고오길

 

 

https://hongjw1938.tistory.com/117

자료구조 - 이분 그래프(Bipartite Graph)

참고한 사이트이다. 

 

해당 사이트에서 설명한 것 처럼

 

모든 노드들이 이렇게 2가지 형태로 나뉘는 것이고, 같은 집합에 속하는 노드들은 서로 연결되면 안된다

그렇다면  이 문제를 푸는 핵심은 색깔이다.

 

그니까, 연결된 노드들에 대해서 인접하게 연결된 노드들은 같은색깔이면 절대 안된다!

 

여기서 헷갈릴 수 있는게, 이분그래프라고 해서 같은 곳에 속하는 노드들이 고정적일거라 생각하는 것이다.

이 그래프에서도 보았듯이, 저 빨간색 범위는, 서로 바뀌어도 괜찮지 않은가?

오른쪽에있느 파란색한게가 빨간색쪽으로 오고, 빨간색 두개는 파란색쪽으로 가고 색깔만 바꿔도 괜찮다는 얘기이다.

 

예제에 먼저나온

 

3 2

1 3

2 3을 보겠다

 

오호 앞선 그림처럼 나오는구만!

 

만약 3번이 빨간색이라하면 1,2번은 파란색인 것

 

두번째는?

 

 

음..

만약 3번이 빨간색이면, 4 2 번은 파란색이고 1번은 빨간색이 되는데

 

 

이상태에서 2번이 파란색이면, 4번은 빨간색이여야 한다

즉 후에 업데이트 시, 4번이 3번과 다시 같은색이 되므로 이건 안돼!

 

 

즉!!

 

우리는

1. 연결된 노드들에 대해서는 인접한 노드들의 색깔은 무조건 달라야 한다

 

2. 방문하지 않은 모든 노드들에 대해서 반복한다.

 

 

 

 

코드를 먼저 보여주겠다

 

#include <iostream>

#include <vector>

#include <string.h>

#include <queue>

#include <algorithm>

using namespace std;

int n, m;

vector<int> v[20002];

bool visited[20002];

int arr[20002] = {0};

void bfs();

int count_ = 0;

int main()

{

    int number;

    cin >> number;

    for (int x = 0; x < number; x++)

    {

        cin >> n >> m;

        for (int i = 0; i < m; i++)

        {

            int x, y;

            cin >> x >> y;

            v[x].push_back(y);

            v[y].push_back(x);

        }

        bfs();

        for (int i = 1; i <= n; i++)

        {

            v[i].clear();       // 그래프 초기화

            visited[i] = false; // 방문 초기화

            arr[i] = 0;         // 색상 초기화 (0=미방문, 1 또는 2)

        }

    }

}

void bfs()

{

    for (int k = 1; k <= n; k++)

    {

        queue<int> q;

        q.push(k);

        if (!visited[k])

        {

            arr[k] = 1;

            visited[k] = true;

            while (!q.empty())

            {

                int x = q.front();

                q.pop();

                int n_c;

                if (arr[x] == 1)//child 노드들에 대한 색깔 정해주기~

                {

                    n_c = 2;

                }

                else if (arr[x] == 2)

                {

                    n_c = 1;

                }

                for (int i = 0; i < v[x].size(); i++)

                {

                    if (!visited[v[x][i]])

                    {

                        visited[v[x][i]] = true;

                        q.push(v[x][i]);

                        arr[v[x][i]] = n_c;

                    }

                }

            }

        }

    }

    for (int i = 1; i <= n; i++)

    {

        for (int j = 0; j < v[i].size(); j++)

        {

            if (arr[i] == arr[v[i][j]])

            {

                cout << "NO\n";

                return;

            }

        }

    }

    cout << "YES\n";

    return;

}

내용 자체는 어렵지 않은데, 꼭 백터와 visited을 초기화 해주는 것을 잊지마라

왠만한 내용은 bfs와 dfs와 같다.