[알고리즘_코딩 테스트_JAVA] 그래프-이분 그래프 판별하기 (JAVA, PYTHON)

본문은 알고리즘 코딩테스트 자바편을 정리한 내용입니다 :)

 

✔ 문제 048 이분 그래프 판별하기

문제 바로가기 💨 

 

⬜ 핵심 아이디어

이분 그래프란?

• 집합이 두 개 있을때, 인접한 노드끼리 서로 다른 집합에 넣을 수 있다면 이분 그래프
• 인접한 노드끼리 서로다른 집합에 들어가게 만들 수 있으면 이분그래프

인접한 노드끼리 같은 집합이 되지 않도록 어떻게 적절히 분할할까?

생각해보면, 트리는 항상 이분 그래프이다. 사이클이 발생하지 않으면 탐색을 하면서 다음 노드를 이번 노드와 다른 집합으로 지정하면 되기 때문이다! 즉, 사이클이 발생하지않으면 이분그래프이다.

단, 사이클이 발생했을때는 이런 이분 그래프가 불가능할 때가 있다. (ex _ 1 -> 2 -> 3 -> 1)

 

기존 탐색 노드에서 탐색한 노드에 다시 접근하게 됐을 때 현재 노드의 집합과 같으면 이분 그래프가 불가능하다는 것으로 판별할 수 있다. 이때, 모든 노드에 대해 DFS 탐색을 해야하는데 이유는 모든 노드가 이어져 있지 않고 여러 개의 부분 그래프로 이뤄진 케이스가 존재 할 수 있기 때문이다.

슈도코드 작성하기

N(테스트 케이스 개수)
IsEven(이분 그래프 판별 변수)

# DFS 구현
DFS:
    visited 리스트에 현재 노드 방문 기록하기
    if 현재 노드의 연결 노드 중 방문 X 노드:
        현재 노드와 다른 집합으로 연결 노드 집합 저장
        DFS(다음 노드)
    elif 이미 방문한노드인데, 현재 나의 노드와 같은 집합:
        이분 그래프 X

for N만큼 반복:
    변수 초기화
    for 엣지만큼 반복:
        인접리스트에 그래프 데이터 저장

for V만큼 반복:
    각 노드에서 DFS 실행 -> 결과가 이분 그래프가 아니면 반복 종료

이분 그래프 여부 출력

JAVA

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

public class Main {
    static ArrayList<Integer>[] A;
    static int[] check;
    static boolean[] visited;
    static boolean IsEven;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        for (int i = 0; i < N; i++) {
            String[] s = br.readLine().split(" ");
            int V = Integer.parseInt(s[0]);
            int E = Integer.parseInt(s[1]);
            A = new ArrayList[V + 1];
            visited = new boolean[V + 1];
            check = new int[V + 1];
            IsEven = true;
            for (int j = 1; j <= V; j++) {
                A[j] = new ArrayList<>();
            }
            for (int j = 0; j < E; j++) { // 인접 리스트 그래프 저장
                s = br.readLine().split(" ");
                int sNode = Integer.parseInt(s[0]);
                int eNode = Integer.parseInt(s[1]);
                A[sNode].add(eNode);
                A[eNode].add(sNode);
            }
            // 주어진 그래프가 1개로 연결돼 있다는 보장이 없으므로 모든 노드에서 수행하기
            for (int j = 1; j <= V; j++) {
                if (IsEven) {
                    DFS(j);
                } else {
                    break;
                }
            }
            if (IsEven) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
        }
    }

    public static void DFS(int node) {
        visited[node] = true;
        for (int i : A[node]) {
            if (!visited[i]) {
                check[i] = (check[node] + 1) % 2;
                DFS(i);
            } else if (check[node] == check[i]) {
                IsEven = false;
            }
        }
    }
}

PYTHON

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def DFS(node):
    global IsEven
    visited[node] = True
    for i in A[node]:
        if not visited[i]:
            # 인접 노드는 같은 집합이 아니므로 다른 집합으로 처리
            check[i] = (check[node] + 1) % 2
            DFS(i)
        # 이미 방문한 노드가 현재 내 노드와 같은 집합이면 이분 그래프 아님
        elif check[node] == check[i]:
            IsEven = False

N = int(input())
IsEven = True

for _ in range(N):
    V, E = map(int, input().split())
    A = [[] for _ in range(V + 1)]
    visited = [False] * (V + 1)
    check = [0] * (V + 1)
    IsEven = True
    
    for i in range(E):
        s, e = map(int,input().split())
        A[s].append(e)
        A[e].append(s)
    
    # 주어진 그래프가 항상 1개가 아니므로 모든 노드에서 수행
    for i in range(1, V + 1):
        if IsEven:
            DFS(i)
        else:
            break
    
    if IsEven:
        print("YES")
    else:
        print("NO")