[C++/LeetCode] Is Graph Bipartite? - using BFS

Daily LeetCoding Challenge for April, Day 29.

 

문제: 이분 그래프(Bipartite Graph) 판단하기

---

이분 그래프 Bipartite Graph

node들을 두개의 집합으로 구분할 수 있고, 같은 집합에 속한 node끼리는 연결되지 않아야 한다.

 

즉 다시 말해서 3색 칠하기와 같은 문제라고 볼 수 있다. 연결되어 있는 노드끼리는 같은 색이 되지 않도록 색칠하는 문제와 같다.

---

아이디어: BFS (or DFS)

BFS를 사용하여 그래프를 전체 탐색하여 연결되어 있는 노드가 같은 색인 경우 false를 return 하면 된다.

 

완성

class Solution {
public:
    void BFS(vector<int> &color, vector<vector<int>> graph, int root, int c, bool &result)
    {
        queue<int> q;
        
        // 미방문 노드에 대해서 BFS를 하므로 방문 처리를 해준다.
        q.push(root);
        color[root] = c;	// 이때 node의 색은 1, -1 두가지 중 하나로 정한다.
        
        while(!q.empty())
        {
            int temp = q.front();
            q.pop();
            
            // 해당 node와 연결된 node들에 대해서 색을 확인한다.
            for(int i = 0;i < graph[temp].size();i++)
            {
            	// 미방문 노드인 경우 색을 현재 node와 다른 색으로 정하고 queue에 추가한다.
                if (color[graph[temp][i]] == 0)
                {
                    color[graph[temp][i]] = color[temp] * -1;
                    q.push(graph[temp][i]);
                }
                // 만약 색이 같은 경우는 (1, -1) 이 아니라 (1, 1) 또는 (-1, -1) 인 경우이므로 
                // 더했을 때의 합이 0이 아니다. 따라서 이 경우 결과를 false로 하고 종료한다.
                else if (color[temp] + color[graph[temp][i]] != 0)
                {
                    result = false;
                    return;
                }
            }
            
        }
    }
    
    // 파라미터로 주어지는 graph는 adjacency list이다.
    // 입력 예시: graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
    
    bool isBipartite(vector<vector<int>>& graph) {
        bool result = true;		// 시작은 일단 true로 만들어 줌
        
        int V = graph.size();   // number of node
        vector<int> color(V, 0);	// node에 어떤 색이 칠해져있는지 확인하기 위함, 방문하지 않은 경우 0
        
        // node와 연결되어 있는 node를 방문하여 연결된 색을 확인한다.
        for(int i = 0;i < V;i++)
        {
            if (result == false)
                break;
            
            // 미방문 노드의 경우에는 BFS를 실행하여 방문 처리를 한다.
            else if (color[i] == 0)
                BFS(color, graph, i, 1, result);
        }
        
        return result;
    }
};

 

점점 문제가...너무 어려워지고 있어... 근데 지난 이틀동안 보다는 할만하네 마침 알고리즘 스터디 하면서 BFS, DFS 해놨더니 할만한듯

내일은 마지막날인데 얼마나 어려울까

 

참고 문헌 및 자료

https://en.wikipedia.org/wiki/Bipartite_graph

Bipartite graph - Wikipedia

https://gmlwjd9405.github.io/2018/08/23/algorithm-bipartite-graph.html