[BOJ/백준] 1707 이분 그래프

● [문제번호 1707] 이분 그래프

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

1707번: 이분 그래프

 

● 알아야 할 것

: vector 자료구조와 메소드

: BFS 넓이 우선 탐색

: DFS 깊이 우선 탐색 (재귀, 비재귀)

 

● 풀이 과정

: 문제에서 설명하는 이분그래프가 무엇인지 이해가 바로 되지 않아서 알아보니

그래프를 2가지 집합으로 나누는데

각 정점(기준)에 연결된 정점들은 정점(기준)과 다른 집합으로 나뉘는 것이다.

 

쉽게 이해하자면

두 집합을 빨강(1)과 초록(-1)로 나눌 것이다.

그런데 조건은 빨강색 정점과 이어진 모든 정점은 초록색이다.

그리고 초록색 정점과 이어진 모든 정점은 빨강색이다.

 

이러한 조건을 만족하면 이분 그래프이다.

해당 문제 '예제 입력1' 

 

그래서 BFS, DFS의 방법을 이용하여

현재 방문한 정점을 기준으로 방문할 다음 정점이

1. 미방문 : 현재 정점의 반대 색상 저장

2. 방문했는데 현재 정점의 반대 색상인 경우 : Continue

3. 방문했는데 현재 정점의 색상인 경우 : 이분 그래프 불가능! (더 이상 탐색X)

 

● 주의 할 것

: 각 테스트케이스 마다 정점, 간선의 갯수가 다르므로

정점, 간선, 방문기록 모두 초기화하는 작업을 해야한다.

 

: 그래프의 모든 정점이 이어져있다는 보장이 없으므로

한 번씩 모두 체크를 해야한다.

 

● 참고 할 것

: NULL

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// vertex : 각 정점에 연결된 정점집합
// visited : 정점의 방문기록
// sol : 이분 그래프인지 결정
vector<int> vertex[20001];
vector<int> visited;
int K, V, E, sol = 1;

// 넓이 우선 탐색
// 기본적인 작성 형태로 구현
int bfs(int start)
{
    queue<int> q;
    
    visited[start] = 1;
    q.push(start);
    
    while(!q.empty())
    {
        int from = q.front();
        q.pop();
        
        for(int i = 0; i < vertex[from].size(); i++)
        {
            int to = vertex[from][i];
            
            if(visited[to] == 0)
            {
                // from 정점의 색상(1 또는 -1) 의 반댓값(-1 또는 1) 저장
                visited[to] = visited[from] * -1;
                q.push(to);
            }
            else if(visited[to] == visited[from])
                // 이분 그래프가 아닌 경우
                return 0;
        }
    }
    
    // 이분 그래프로 만들어 지는 경우
    return 1;
}

// 깊이 우선 탐색 (비재귀)
// 기본적인 작성 형태로 구현
int dfs(int start)
{
    stack<int> s;
    
    visited[start] = 1;
    s.push(start);
    
    while(!s.empty())
    {
        int from = s.top();
        s.pop();
        
        for(int i = 0; i < vertex[from].size(); i++)
        {
            int to = vertex[from][i];
            
            if(visited[to] == 0)
            {
                // from 정점의 색상(1 또는 -1) 의 반댓값(-1 또는 1) 저장
                visited[to] = visited[from] * -1;
                s.push(to);
            }
            else if(visited[to] == visited[from])
                // 이분 그래프가 아닌 경우
                return 0;
        }
    }
    
    // 이분 그래프로 만들어 지는 경우
    return 1;
}

// 깊이 우선 탐색 (재귀)
// 기본적인 작성 형태에서 이분그래프인지 확인 작업 추가
int dfs_recursive(int from, int color)
{
    for(int i = 0; i < vertex[from].size(); i++)
    {
        int to = vertex[from][i];
        
        // 가능한 깊이까지 간 재귀가 가져오는 반환값이
        // 이분그래프 가능(1)인지 불가능(0)인지 판단하는 변수
        int flag = 1;
        
        if(visited[to] == 0)
        {
            // from 정점의 색상(1 또는 -1) 의 반댓값(-1 또는 1) 저장
            visited[to] = color * -1;
            flag = dfs_recursive(to, color * -1);
        }
        else if(visited[to] == visited[from])
            // 이분 그래프가 아닌 경우
            flag = 0;
        
        // 이분 그래프가 아닌 경우로 더이상 진행X
        if(flag == 0)
            return 0;
    }
    
    // 현재까지 진행한 재귀가 이분 그래프로 만들어지는 경우
    return 1;
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> K;
    
    // 테스트 케이스만큼 반복
    // (테스트 케이스마다 정점, 간선이 다르므로 초기화에 주의한다)
    for(int k = 0; k < K; k++)
    {
        cin >> V >> E;
        
        // 간선 입력
        for(int e = 0; e < E; e++)
        {
            int a, b;
            cin >> a >> b;
            
            vertex[a].push_back(b);
            vertex[b].push_back(a);
        }
        
        // 정점 생성
        visited.assign(V + 1, 0);
        
        // 그래프 탐색으로 이분 그래프인지 판단
        for(int i = 1; i <= V; i++)
            if(visited[i] == 0)
            {
                visited[i] = 1;
                // {DFS_재귀, DFS_비재귀, BFS} 중에 선택
                sol *= dfs_recursive(i, 1);
                // sol *= dfs(i);
                // sol *= bfs(i);
            }
        
        // sol (1 : 이분 그래프 가능 / 0 : 이분 그래프 불가능)
        if(sol)
            cout << "YES\n";
        else
            cout << "NO\n";
        
        // 다시 초기화
        sol = 1;
        
        // 정점 다시 초기화
        visited.clear();
        
        // 간선 다시 초기화
        for(int v = 0; v < V + 1; v++)
            vertex[v].clear();
    }
    
    return 0;
}

 

 

● [백준] - [알고리즘 기초 2/2] - [600 - 그래프 1] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	13023	ABCDE	https://pirateturtle.tistory.com/269
2	1260	DFS와 BFS	https://pirateturtle.tistory.com/270
3	11724	연결 요소의 개수	https://pirateturtle.tistory.com/271
4	1707	이분 그래프	https://pirateturtle.tistory.com/272
5	2667	단지번호붙이기	https://pirateturtle.tistory.com/273
6	4963	섬의 개수	https://pirateturtle.tistory.com/274
7	2178	미로 탐색	https://pirateturtle.tistory.com/275
8	7576	토마토	https://pirateturtle.tistory.com/276
9	7562	나이트의 이동	https://pirateturtle.tistory.com/277