백준 1707번: 이분 그래프

문제

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

1707번: 이분 그래프

---

풀이

그래프의 정점의 집합을 둘로 분할했을 때 각 집합에 속한 정점끼리 서로 인접하지 않도록 분할할 수 있는 그래프인 이분 그래프(Bipartite Graph)를 판별하는 문제입니다.

---

접근

처음에 문제를 다음 그림과 같이 잘못 이해했습니다.

그래프를 위와 같이 둘로 나눌 수 있다면 이분 그래프인줄 알았습니다.

 

그래서 유니온 파인드 알고리즘으로 접근하고자 했지만 예제에서부터 답이 다르게 출력됐습니다.

이분 그래프는 다음과 같습니다.

연결된 순서대로 정점의 색을 이분법적으로 칠할 수 있는 그래프

번호가 1부터 6까지 있는 정점이 오름차순으로 순서대로 1개씩만 연결돼있다면 이분 그래프라고 볼 수 있습니다.

이분 그래프가 아닌 단적인 예는 아래와 같습니다.

4번 정점에 5번과 6번 정점이 연결돼있고 5번 정점에도 6번 정점이 연결돼있는 그래프

4번 정점을 파란색으로 칠했을 때 5번과 6번 정점은 빨간색으로 칠해야 합니다.

하지만 5번 정점이 빨간색이기 때문에 6번 정점은 파란색이어야 하고 이때 일종의 충돌이 발생하게 됩니다.

---

코드

자바

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {

    static int v, e;
    static boolean bipartited;
    static boolean[] visited, grouped;
    static ArrayList<Integer>[] list;

    public static void dfs(int idx, boolean side) {
        if (!bipartited) return; // (3)
        visited[idx] = true;
        grouped[idx] = side;
        if (list[idx] != null) {
            for (int e : list[idx]) { // (4)
                if (!visited[e]) {
                    dfs(e, !side);
                } else if (grouped[idx] == grouped[e]) {
                    bipartited = false;
                    return;
                }
            }
        }
    }

    @SuppressWarnings("unchecked")
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int k = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        while (k-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            v = Integer.parseInt(st.nextToken());
            e = Integer.parseInt(st.nextToken());
            visited = new boolean[v + 1];
            grouped = new boolean[v + 1];
            list = new ArrayList[v + 1];
            for (int i = 1; i <= v; i++) {
                list[i] = new ArrayList<Integer>();
            }
            for (int i = 0; i < e; i++) {
                st = new StringTokenizer(br.readLine(), " ");
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                list[x].add(y);
                list[y].add(x);
            }
            bipartited = true; // (1)
            for (int i = 1; i <= v; i++) {
                if (!visited[i]) { // (2)
                    dfs(i, true);
                }
            }
            if (bipartited) sb.append("YES\n");
            else sb.append("NO\n");
        }
        System.out.print(sb);
    }
}

(1) 해당 그래프가 이분 그래프인지 아닌지를 나타내는 bipartited를 true로 초기화해줍니다.

테스트 케이스의 개수 k가 1이 아닐 수도 있기 때문에 매번 초기화해줍니다.

 

(2) i를 포함한 for문을 이용하여 모든 정점의 방문 여부를 확인합니다.

모든 정점이 전부 연결돼있다는 보장이 없기 때문에 확인해줘야 합니다.

i번 정점을 방문한 적이 없다면 dfs 함수를 실행합니다. 함수의 매개변수 idx는 현재 탐색중인 정점의 번호를 뜻하며 side는 해당 정점의 색입니다.

위의 그림에서 정점을 빨간색과 파란색으로 나눴는데 이 코드에서 true를 빨간색, false를 파란색으로 생각하시면 될 것 같습니다.

 

(3) bipartited가 false라면 이미 이분 그래프를 완성할 수 없다는 것을 확인했다는 뜻이기 때문에 함수를 종료합니다.

아직 true라면 idx번 정점의 방문처리를 해준 후에 해당 정점을 side색(true or false)으로 칠합니다.

 

(4) 해당 정점에 연결된 다른 정점(e번 정점)이 있다면 foreach문을 통해 그래프를 탐색합니다.

e번 정점을 방문한 적이 없다면 dfs 함수를 재귀적으로 실행합니다. 이때 side는 다음 정점의 색은 반대로 칠해야하기 때문에 !side를 매개변수로 사용합니다.

e번 정점을 방문한적이 있다면 해당 정점의 색과 현재 정점의 색을 비교합니다. 만약 두 개의 색이 같다면 충돌이 일어난 것이므로 bipartited를 false로 초기화해준 뒤에 함수를 종료합니다.

 

모든 정점의 탐색이 끝났다면 이분 그래프라면 "YES"를, 아니라면 "NO"를 Stringbuilder sb에 넣었다가 한꺼번에 출력합니다.

C언어

#include <stdio.h>
#include <stdlib.h>
int bipartited, *visited, *grouped;
typedef struct node {
	int x;
	struct node* next;
} node;
void add(node* target, int x) {
	node* now = (node*)malloc(sizeof(node));
	now->x = x;
	now->next = target->next;
	target->next = now;
	return;
}
node* list[20001];
void dfs(int idx, int side) {
	if (!bipartited) return;
	visited[idx] = 1;
	grouped[idx] = side;
	node* curr = list[idx]->next;
	while (curr != NULL) {
		int e = curr->x;
		if (!visited[e]) {
			dfs(e, !side);
		}
		else if (grouped[idx] == grouped[e]) {
			bipartited = 0;
			return;
		}
		curr = curr->next;
	}
}
main() {
	int k, cnt = 0;
	scanf("%d", &k);
	int* result = (int*)malloc(sizeof(int) * k);
	while (k--) {
		int v, e;
		scanf("%d %d", &v, &e);
		visited = (int*)malloc(sizeof(int) * (v + 1));
		grouped = (int*)malloc(sizeof(int) * (v + 1));
		for (int i = 1; i <= v; i++) {
			list[i] = (node*)malloc(sizeof(node));
			list[i]->next = NULL;
			visited[i] = 0;
		}
		for (int i = 0; i < e; i++) {
			int x, y;
			scanf("%d %d", &x, &y);
			add(list[x], y);
			add(list[y], x);
		}
		bipartited = 1;
		for (int i = 1; i <= v; i++) {
			if (!visited[i]) {
				dfs(i, 1);
			}
		}
		if (bipartited) result[cnt++] = 1;
		else result[cnt++] = 0;
	}
	for (int i = 0; i < cnt; i++) {
		printf(result[i] ? "YES\n" : "NO\n");
	}
}

자바를 이용한 풀이와 동일합니다. ArrayList 배열은 연결리스트를 이용하여 구현했습니다.

 

---

결론

문제를 이해하기 위한 구글링이 필요했던 문제였습니다. 언제나 문제의 설명이 친절하게 나오진 않을 것이란 각오로 문제를 천천히 읽으면서 이해하는 독해력을 길러야겠다고 생각했습니다.