[백준/BOJ] 1707번: 이분 그래프 ( 깊이 우선 탐색, DFS 활용법 ) - C++ 문제 풀이

 

문제 설명

 

문제 링크: https://www.acmicpc.net/problem/1707

 

풀이

이 문제는 주어진 그래프가 이진 그래프( Bipartite Graph )인지 판단하는 문제입니다.

 

이진 그래프는 그래프의 모든 정점을 두 그룹으로 나눌 수 있는 그래프를 말합니다.

예를 들어, 한 정점이 그룹 1에 속하면, 그와 인접한 모든 정점은 그룹 2에 속해야 합니다.

 

만약, 모든 정점을 두 그룹으로 나눌 수 있다면, 모든 정점을 인접한 정점과 다른 색상으로 칠할 수 있다는 얘기가 됩니다.

 

이와 비슷한 문제로 4색 문제가 있습니다.

4색 문제는 평면을 유한 개의 부분으로 나누어 각 부분에 색을 칠할 때, 서로 맞닿은 부분을 다른 색으로 칠한다면 네 가지 색으로 충분하다는 정리입니다.

 

이 문제 풀이는 깊이 우선 탐색법과 너비 우선 탐색법 모두 가능합니다.

여기서는 깊이 우선 탐색법으로 풀었습니다.

 

깊이 우선 탐색에 관한 내용은 여기에서 볼 수 있습니다.

[백준/BOJ] 24480번: 깊이 우선 탐색 2 ( DFS, Depth-First Search ) - C++ 문제 풀이

 

먼저, 깊이 우선 탐색을 코드로 작성하면 다음과 같습니다.

#define SIZE 20001
#define GROUP1  1	// 두 종류의 그룹
#define GROUP2  2

typedef short MTYPE;

char visited[SIZE];	// 방문한 정점을 그룹으로 표시
vector<MTYPE> graph[SIZE];	

bool DFS( MTYPE v, char group ){

    visited[v] = group;	

    for( MTYPE x : graph[v]){	// 정점 v에 인접한 정점들을 탐색
        
        if ( !visited[x]){

            if (!DFS(x, 3 - group))	// 정점 x를 v와 다른 그룹으로 표시
                return false;
        }
        else{	// 이미 방문한 정점은 같은 그룹에 속해 있는지 확인
        
            if (visited[x] == group)    // 인접한 정점은 서로 다른 그룹이어야 한다.
                return false;		// 인접한 정점이 같은 그룹이면 이분 그래프가 아님
        }
    }

    return true;
}

이 함수는 해당 정점 v를 그룹 1 또는 그룹 2로 나누어 표시하는 함수입니다.

그리고 깊이 우선 탐색으로, v와 인접한 정점을 모두 순환합니다.

 

만약, 이웃한 정점을 탐색 중인 정점 v의 그룹과 다른 그룹으로 설정할 수 없다면 false를 반환합니다.

false는 이 그래프가 이분 그래프가 아님을 나타냅니다.

 

이제, 위의 깊이 우선 탐색 함수를 호출하는 main 함수를 보겠습니다.

int main(){
    
    int K, V, E;    // show case 개수, vertex 개수, edge 개수
    MTYPE A, B;     // edge 정보

    K = readInt();

    for( int i = 0; i < K; i++){	// 한 번에 여러개의 문제가 같이 입력
        
        V = readInt();
        E = readInt();

        for( int j = 0; j < E; j++){	// 그래프 구성
        
            A = readInt();
            B = readInt();

            graph[A].push_back(B);
            graph[B].push_back(A);
        }

        bool bRet = true;
        for( int j = 1; j <= V; j++){
            
            if ( !visited[j]){  // 모든 정점을 확인할 것

                bRet = DFS(j, GROUP1);	// 깊이 우선 탐색
                
                if (!bRet)	// 이분 그래프가 아니면 탐색 중지
                    break;
            }
        }

        if ( bRet) cout << "YES\n";	// 이분 그래프 탐색 결과 표시
        else cout << "NO\n";

        // 이번 문제를 풀기 위한 데이터를 초기화
        memset( visited, 0, sizeof(char) * SIZE);
        for( int j = 1; j <= V; j++){
            graph[j].clear();
        }
    }

    return 0;
}

문제를 푸는 기본 틀이, 위에서 링크로 소개한 "깊이 우선 탐색 기본 문제"와 유사함을 알 수 있습니다.

다른 점이 있다면, 각 정점을 방문하는 순서를 기록하는 대신, 정점이 속한 그룹을 기록한다는 점 정도일 것입니다.

 

참고로, 데이터를 입력받는데 cin 객체를 사용하면, 대부분의 시간이 입력받는 시간으로 지나가버리기 때문에

한 번에 데이터를 읽어오는 방식을 사용했습니다.

 

소스 코드

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

// 입출력 소스 --------------------------------------------
#define WBUF_SIZE (1 << 20)

char rbuf[WBUF_SIZE];
int ridx, nidx;

inline char read() {
	if (ridx == nidx) {
		nidx = fread(rbuf, 1, 1 << 20, stdin);
		if (!nidx) return 0;
		ridx = 0;
	}
	return rbuf[ridx++];
}
inline int readInt() {
	int sum = 0;
	char now = read();
	bool flg = false;

	while (now <= 32) now = read();
	if (now == '-') flg = true, now = read();
	while (now >= 48) sum = sum * 10 + now - '0', now = read();

	return flg ? -sum : sum;
}
int unitSize(int n) { // 자리 수
	if (n < 0)n = -n;
	int ret = 1;
	while (n >= 10) {
		ret++;
		n /= 10;
	}
	return ret;
}

//----------------------------------------------------------

#define SIZE 20001
#define GROUP1  1
#define GROUP2  2

typedef short MTYPE;

char visited[SIZE];
vector<MTYPE> graph[SIZE];

bool DFS( MTYPE v, char group ){

    visited[v] = group;

    for( MTYPE x : graph[v]){
        
        if ( !visited[x]){

            if (!DFS(x, 3 - group))
                return false;
        }
        else{
            if (visited[x] == group)    // 인접한 정점은 서로 다른 그룹이어야 한다.
                return false;
        }
    }

    return true;
}

int main(){
    
    int K, V, E;    // show case 개수, vertex 개수, edge 개수
    MTYPE A, B;     // edge 정보

    K = readInt();

    for( int i = 0; i < K; i++){
        
        V = readInt();
        E = readInt();

        for( int j = 0; j < E; j++){
        
            A = readInt();
            B = readInt();

            graph[A].push_back(B);
            graph[B].push_back(A);
        }

        bool bRet = true;
        for( int j = 1; j <= V; j++){
            
            if ( !visited[j]){  // 모든 정점을 확인할 것

                bRet = DFS(j, GROUP1);
                if (!bRet)
                    break;
            }
        }

        if ( bRet) cout << "YES\n";
        else cout << "NO\n";

        // clear previous data
        memset( visited, 0, sizeof(char) * SIZE);
        for( int j = 1; j <= V; j++){
            graph[j].clear();
        }
    }

    return 0;
}