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

📌백준 1707 이분그래프
https://www.acmicpc.net/problem/1707

저번에 인접행렬을 사용해봤으니 이번엔 인접리스트를 사용해보자.
이번엔 visited에 방문했다는 표시 1 말고 색깔을 넣을 것이다. 빨간색이면 RED(2), 파란색이면 BLUE(3)를 넣었다.

• 인접리스트, 방문기록, 노드 수, 간선 수를 전역에다 선언해준다. 인접리스트는 vector로 만들어주었다.
• main()에서 테스트케이스를 입력받고 각 테스트케이스별 노드 수, 간선 수와 각각 노드를 입력받았다. 그리고 인접리스트에 넣어줌

1. DFS

• 빠짐없이 방문하기 위해서 1부터 N까지 다 돌려줌 대신 방문기록 있는 것들만 DFS 돌려줌
• 처음 방문하는 점이면 방문기록에 RED 넣어줌
• 연결된 점 탐색하러 가는데 연결된 점도 방문한 적이 없다? 그럼 여기서 조건을 걸어줌. 탐색 시작한 노드가 RED라면 연결된 점에는 BLUE를, BLUE라면 RED를 넣어줌.
• 그리고 요소별로 방문. 이것을 반복함(재귀)

2. BFS

• 큐 만들어주고 시작점 큐에 push
• 큐 맨 앞 값 복사해주고 큐 pop
• 큐 맨 앞 값이 RED다? 그러면 인접리스트에 연결된 노드들은 모두 BLUE로 넣어줌. (BLUE면 RED로)

• check()함수로 이분그래프 검사를 할 것이다. 인접한 노드와 시작점 노드가 색이 같으면 이분그래프 X. 한번이라도 같은게 있으면 바로 리턴해버림
• 그리고 중요한 것이 있다. 이 문제는 테스트케이스가 있으므로 인접리스트와 방문기록을 여러 번 써야한다는 것. 그러기 위해서는 초기화 작업이 필요하므로 memset을 사용해준다.

DFS 풀이

#include <iostream>
#include <vector>
#include <string.h>
using namespace std;

#define RED 2
#define BLUE 3

vector<int> vect[20001]; //인접리스트
int visited[20001];      //방문기록
int V, E;

/* DFS 실행 */
void DFS(int start)
{
    //방문안한 점이면 RED
    if (visited[start] == 0)
        visited[start] = RED;

    //연결된 점들 방문
    for (int i = 0; i < vect[start].size(); i++)
    {
        int idx = vect[start][i];
        if (visited[idx] == 0) //방문 안한 점이면
        {
            //요소에 방문기록 남김(색칠하기)
            if (visited[start] == RED)
                visited[idx] = BLUE;
            else if (visited[start] == BLUE)
                visited[idx] = RED;

            //요소별로 방문
            DFS(idx);
        }
    }
}

/* 이분그래프 검사 */
int check()
{
    //인접한 노드와 색이 같으면 이분그래프 X
    for (int i = 1; i <= V; i++)
    {
        //연결된게 자기자신 뿐일 경우엔 size가 0이라서 돌아가지 않는다.
        for (int j = 0; j < vect[i].size(); j++)
        {
            int idx = vect[i][j];
            if (visited[i] == visited[idx]) 
            {
                return false;
            }
        }
    }
    return true;
}

int main()
{
    int T;    //테스트케이스
    int u, v; //노드 담을 변수

    cin >> T;
    while (T--)
    {
        cin >> V >> E;
        for (int i = 0; i < E; i++)
        {
            cin >> u >> v;
            vect[u].push_back(v);
            vect[v].push_back(u);
        }

        
        //빠짐없이 방문하기 위해 1부터 원소 개수까지 다 방문해봄
        for (int i = 1; i <= V; i++)
        {
            if (visited[i] == 0)
                DFS(i);
        }

        if (check() == 0) //이분그래프인지 검사
            cout << "NO\n";
        else
            cout << "YES\n";

        memset(visited, 0, sizeof(visited));
        memset(vect, 0, sizeof(vect));
    }
}

BFS 풀이

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;

#define RED 1
#define BLUE 2

vector<int> vect[20001];
int visited[20001];
int V, E;

void BFS(int start)
{
    visited[start] = RED;
    queue<int> q;
    q.push(start);

    while(q.size()!=0) //큐가 빌 때 까지 반복(전체)
    {
        int now = q.front();
        q.pop();
        for(int i=0; i<vect[now].size(); i++)
        {
            if(visited[vect[now][i]] == 0)
            {
                q.push(vect[now][i]);

                if(visited[now] == RED) visited[vect[now][i]] = BLUE;
                else if(visited[now] == BLUE) visited[vect[now][i]] = RED;
            }
        }

    }

}

bool check()
{
    for (int i = 1; i <= V; i++)
    {
        for (int j = 0; j < vect[i].size(); j++)
        {
            if (visited[i] == visited[vect[i][j]])
                return false;
        }
    }
    return true;
}

int main()
{
    int K, u, v;
    cin >> K;

    while (K--)
    {
        cin >> V >> E;
        for (int i = 0; i < E; i++)
        {
            cin >> u >> v;
            vect[u].push_back(v);
            vect[v].push_back(u);
        }

        //빠짐없이 방문하기 위해 노드 개수만큼 BFS 돌려줘야함
        for (int i = 1; i <= V; i++)
        {
            if (visited[i] == 0)
            {
                BFS(i);
            }
        }

        //이분그래프 검사
        if (check())
            cout << "YES\n";
        else
            cout << "NO\n";

        memset(visited, 0, sizeof(visited));
        memset(vect, 0, sizeof(vect));
    }
}