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

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

1707번: 이분 그래프

 

해설 

먼저 이 문제를 풀 때 가장 중요한 것은 이분 그래프가 무엇인지 정확히 이해하는 것인데요. 문제에서 정의한 이분 그래프는 아래와 같습니다.

그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph)라 부른다.

 

즉, 그래프의 모든 정점을 크게 두 집합으로 나눌건데, 인접한 녀석들은 서로 다른 집합에 존재하게 만들어야한다는 것입니다. 어떻게 하면 해당 그래프가 이분 그래프가 될 수 있는지 판단할 수 있을까요?

 

저는 BFS를 이용해서 문제를 풀었는데요. 우선 모든 정점은 단 두 개의 집합으로만 나뉘어야 하기 때문에 한 집합의 번호를 '1'로 하면 다른 집합의 번호를 '-1'로 설정할 수 있고 이 둘은 자신의 값에 -1을 곱해줌으로써 전환될 수 있다는 장점이 있습니다.

 

그리고나서 모든 정점에 대해 자신이 속한 집합의 번호를 '0'으로 초기화하고, 1번 정점부터 BFS 탐색을 하면서 같은 레벨에 존재하는 정점은 자신과 반대되는 정점으로 체크해줍니다. 만약 N번째 정점이 이미 방문된 정점이라면 다시 BFS를 돌릴 필요는 없겠죠?

 

한편 BFS를 수행하다가 다음 레벨에 존재하는 정점 중 하나가 이미 방문한 정점이라면(그룹 번호가 0이 아닐 때) 현재 정점이 속한 그룹과 다음 정점이 속한 그룹이 같은지 봐야 합니다. 같다면 이분 그래프를 만드는 데 실패한 것이죠.

 

코드는 아래와 같습니다. group이라는 배열(리스트)가 각 정점의 그룹 번호를 저장하고 있습니다.

 

[풀이 - 파이썬]

from collections import deque
import sys
input = sys.stdin.readline

def bfs(start, group):
    q = deque()
    q.append((start, 1)) # 시작 지점과 해당 지점의 그룹번호
    group[start] = 1

    while q:
        curr, currGroup = q.popleft()
        for adj in graph[curr]:
            if group[adj] == 0:
                # 방문 표시를 하고 반대 그룹에 편성
                group[adj] = -currGroup
                q.append((adj, -currGroup))
            else:
                # 이미 방문을 한 정점이 같은 그룹에 있는지 확인
                if group[adj] == currGroup:
                    return False
    return True

k = int(input())
for _ in range(k):
    v, e = map(int, input().split())
    graph = [[] for _ in range(v+1)]
    for _ in range(e):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)

    group = [0]* (v+1) # 각 정점들이 속한 그룹을 담는 배열
    answer = "YES"
    for i in range(1, v+1):
        if group[i] == 0:
            if not bfs(i, group):
                answer = "NO"
                break
    print(answer)

 

 

[풀이 - 자바]

package PS;

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

public class B_1707 {
    static ArrayList<ArrayList<Integer>> graph; // 그래프
    static int[] group;
    static int k,v,e;

    public static boolean bfs(int start){
        LinkedList<Node> q = new LinkedList<>();
        q.add(new Node(start, 1));
        group[start] = 1;

        while(!q.isEmpty()){
            Node curr = q.pollFirst();
            for(Integer adj : graph.get(curr.index)){
                if(group[adj] == 0){
                    // 방문 표시를 하고 반대 그룹에 편성
                    group[adj] = -curr.group;
                    q.add(new Node(adj, -curr.group));
                }else{
                    // 이비 방문을 한 정점이 같은 그룹에 있으면 실패
                    if(group[adj] == curr.group){
                        return false;
                    }
                }
            }
        }
        return true;
    }
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        k = Integer.parseInt(br.readLine());
        while(k-- > 0){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int v = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            graph = new ArrayList<>();
            for(int i = 0; i < v+1; i++){
                graph.add(new ArrayList<>());
            }
            for(int i = 0; i < e; i++){
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                graph.get(a).add(b);
                graph.get(b).add(a);
            }
            // 각 정점이 속한 그룹을 기록하는 배열
            group = new int[v+1];
            String answer = "YES";
            for(int i = 1; i < v+1; i++){
                // 아직 방문하지 않은 노드에 대해
                if(group[i] == 0){
                    if(!bfs(i)) answer = "NO";
                }
            }
            System.out.println(answer);
        }
    }
    static class Node{
         int index, group;
         Node(int index, int group){
            this.index = index;
            this.group = group;
        }
    }
}