백준 1707 이분 그래프(dfs)

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

1707번: 이분 그래프

#include <iostream>
#include <vector>
#define RED 1
#define BLUE 2

using namespace std;

const int MAX = 20000 + 1;
vector<int> graph[MAX];
int visited[MAX];
int V, E;

void dfs(int x)
{
    if (!visited[x])
        visited[x] = RED; //BlUE를 넣어도 되지만 그냥 RED를 넣음.

    for (int i = 0; i < graph[x].size(); i++)
    {
        int next = graph[x][i];
        if (!visited[next])
        {
            if (visited[x] == RED)
                visited[next] = BLUE;
            else if (visited[x] == BLUE)
                visited[next] = RED;
            dfs(next);
        }
    }
}

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int testcase;
    cin >> testcase;
    while (testcase--)
    {
        cin >> V >> E;
        for (int i = 0; i < E; i++)
        {
            int node1, node2;
            cin >> node1 >> node2;
            graph[node1].push_back(node2);
            graph[node2].push_back(node1);
        }
        for (int i = 1; i <= V; i++)
        {
            if (!visited[i])
                dfs(i);
        }
        if (isBipartiteGraph())
            cout << "YES"
                 << "\n";
        else
            cout << "NO"
                 << "\n";
        for (int i = 0; i <= V; i++)
        {
            visited[i] = 0;
            graph[i].clear();
        }
    }
}

참고한 사이트)https://jdselectron.tistory.com/51

[백준 1707, c++] 이분 그래프(bfs,dfs)

https://woovictory.github.io/2020/01/26/Bipartite-Graph/

[알고리즘] 이분 그래프

어려웠다....

 

항상 n*n 혹은 n*m 배열이 주어지면 거기에서 dfs를 돌리는 문제만 풀어봤는데 이 문제는 각 행마다 열이 다르다. (그래프이기 때문에 각 노드마다 연결된 edge의 개수가 다르기 때문.)

 

각 노드마다 칠해질 색깔을 체크하면 됐기 때문에 visited 배열은 1차원으로도 충분했다.

 

RED와 BLUE를 그냥 숫자 2, 3으로 표현해도 되지만 저런 식의 표현이 훨씬 더 이해가 쉽기 때문에 효율적인 것 같다.

 

항상 주의해야할 점은  node들의 번호는 보통 1부터 시작한다. 하지만, graph를 vector로 설정해서 push_back하게 되면 0번째 배열에서부터 입력이 시작된다. 따라서, 이 차이를 항상 염두해두고 for loop를 작성해야 한다. 헷갈리기 쉽상이다.

 

코드 혹은 풀이 과정이 어렵지는 않기 때문에 코드를 보면 충분히 이해 가능하다. 하지만 이런 종류의 문제를 처음본 나로서는 좀 많이 어려웠다. 여러번 풀면서 각 행(노드)마다 다른 열(엣지)을 가지는 그래프에 관련된 알고리즘 문제를 푸는데 익숙해져야한다.