Posted 2021-02-15Algorithm / Baekjoon7 minutes read (About 991 words)0 visits

Baekjoon 1707 (이분 그래프) + 그래프 저장 방법

Baekjoon 1707, 백준 1707 문제의 본인 풀이입니다!
문제는 아래의 링크에서 확인할 수 있습니다.
문제보기

#include <cstdio>
#include <cstring>
#include <vector>

#define MAX_V 20000
#define NOT_VISITED 0
#define WHITE 1
#define BLACK 2

std::vector<int> graph[MAX_V + 1];
// graph[i]: vector of dots connected with dot i

int colors[MAX_V + 2];  // 0: NOT_VISITED, 1: WHITE, 2: BLACK
bool isBip;

void init() {
    isBip = true;
    for(int i = 0; i <= MAX_V; i++) {
        graph[i].clear();
    }
    memset(colors, NOT_VISITED, sizeof(colors));
}

void dfs(int start) {
    for(int i = 0; i < graph[start].size(); i++) {
        int tempDot = graph[start][i];
        if(colors[tempDot] == NOT_VISITED) {
            // if not visited, give an opposite color with mine
            if(colors[start] == WHITE) colors[tempDot] = BLACK;
            else if(colors[start] == BLACK) colors[tempDot] = WHITE;
            dfs(tempDot);
        }
        else if(colors[tempDot] == colors[start]) {
            // if two connected dots have the same color, this graph cannot be a Bipartite Graph
            isBip = false;
            return;
        }
    }
}

int main() {
    int testNum;
    scanf("%d", &testNum);

    while(testNum--) {
        int V, E;
        scanf("%d %d", &V, &E);
        init();

        while(E--) {
            int a, b;
            scanf("%d %d", &a, &b);
            // save the connection a-b to 'graph'
            graph[a].push_back(b);
            graph[b].push_back(a);
        }

        for(int i = 1; i <= V; i++) {
            if(colors[i] == NOT_VISITED) {
                // if dot i is not visited, start dfs
                // Considering a non-connected graph
                colors[i] = WHITE;
                dfs(i);
            }
        }

        if(isBip) printf("YES\n");
        else printf("NO\n");
    }
}

문제를 보고 DFS로 해결해야겠다는 아이디어 자체는 쉽게 떠올랐다. 점들에 색칠놀이를 해 주면 되기 때문이다. 사실, 이분그래프(Bipartite Graph)의 정의는 인접한 점들은 다른 색이 되도록 칠할 수 있는 그래프 이다. 그리고 이는 본 문제에서 준 조건인 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프 와 동치이다.

그래서 잘 구현만 해주면 됐는데, 생각보다 여기서 엄청난 삽질을 했다. 결론적으로 데이터 저장을 너무 바보처럼 하고 있었다! 오랜만이라 그래프 정보를 저장하는 것도 까먹고 무식하게 std::pair 로 쑤셔넣고 있었다.. Adjacency List로 넣어 주니 훨씬 간결하게 해결할 수 있었다. Linked List까지 구현할 필요도 없었고 그냥 std::vector 들의 array로 구현해도 충분했다. ~~이걸 부르는 다른 이름이 있었나?~~

문제에 대한 큰 틀의 참고사항들은 다음과 같다.

연결그래프가 아닐 수 있어서 for 문으로 전체 점에 대한 DFS를 돌려주어야 한다. 실제로 이 문제의 ‘틀렸습니다’의 단골 사유라고 한다.
본인은 이런 문제 유형상 DFS가 효율이 더 좋을 것 같아서 DFS로 구현을 시도하고 성공했지만, 사실 BFS로 돌려도 상관 없다. 어차피 건드릴 수 있는 모든 점들을 들러서 색칠해 주어야 하기 때문이다.

아래는 그래프 정보를 저장하는 가장 유명한 세 가지 방법인 Binary-relationship list, Adjacency Matrix와 Adjacency List를 정리해 두겠다. 출처는 아래의 2020-2학기에 들었던 이병영 교수님의 ‘자료구조의 기초’ 수업 메모..

그래프 정보를 저장하는 세 방법