• 개인 공부 목적으로 작성한 포스팅입니다.
  • 아래 출처를 참고하여 작성하였습니다. :)

문제: 이분 그래프

DFS 알고리즘을 사용해서 이분 그래프인지 아닌지 확인할 수 있습니다.

이분 그래프란

  1. 인접한 노드는 서로 다른 색의 노드로 구분되어야 합니다.
  2. 그래프 내의 모든 노드를 두 가지 색으로만 칠할 수 있는 그래프를 의미합니다.

문제 해결 방법

  1. DFS로 아무 노드나 방문하면서 A색깔을 칠해줍니다.
  2. 현재 노드와 인접한 노드를 방문하면서 현재의 색깔(A색깔)과 다른 B색깔로 칠해줍니다.
    • 인접 노드 상태 확인 시, 이미 방문했는데 A색깔로 칠해져있다면 이 그래프는 이분 그래프로 만들 수 없습니다.
    • A색깔, B색깔의 경우 1, -1로 표시하면서 다음 노드를 방문할 때 마다 color = -color로 바꾸면 편합니다.

DFS 결과 합쳐서 리턴하기

아래 같이 코드를 작성하여 DFS 결과를 전부 반영해 결과값을 리턴할 수 있습니다.

  • int 자료형을 리턴하는 것으로 하고 성공 시 0을 리턴, 실패 시 1 이상의 값을 리턴합니다.
  • 자신과 인접한 모든 노드의 dfs값을 합쳐서 자신의 결과값으로 사용하므로 인접 노드에서 한 번이라도 실패 시 1이상의 값을 리턴하게 됩니다.

이런 테크닉으로 return value를 사용하면서 DFS 결과를 합쳐서 리턴할 수 있습니다.

public static int dfs(int node, int color) {

    int result = 0;

    for (Integer nxt : graph[node]) {
        if (visit[nxt] == 0) {
            visit[nxt] = -color;
            result += dfs(nxt, -color);
        } else {
            if (visit[nxt] == color) {
                result += 1;
            }
        }
    }

    return result;
}

코드

import java.io.*;
import java.util.*;


public class Main {

    public static List<Integer>[] graph;
    public static int[] visit;

    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();

        for (int loop = 0; loop < k; ++loop) {

            String[] veInfo = br.readLine().split(" ");
            int v = Integer.parseInt(veInfo[0]);
            int e = Integer.parseInt(veInfo[1]);

            visit = new int[v];
            graph = new List[v];
            for (int i = 0; i < v; ++i) {
                graph[i] = new ArrayList<>();
            }

            for (int i = 0; i < e; ++i) {
                String[] edgeInfo = br.readLine().split(" ");

                int st = Integer.parseInt(edgeInfo[0]);
                int en = Integer.parseInt(edgeInfo[1]);
                st--; en--;
                graph[st].add(en);
                graph[en].add(st);
            }

            boolean result = true;

            for (int i = 0; i < v; ++i) {
                if (visit[i] == 0) {
                    visit[i] = 1;
                    if (dfs(i, 1) != 0) {
                        result = false;
                    }
                }
            }

            if (result) {
                sb.append("YES\n");
            } else {
                sb.append("NO\n");
            }
        }

        System.out.println(sb);
    }

    public static int dfs(int node, int color) {

        int result = 0;

        for (Integer nxt : graph[node]) {
            if (visit[nxt] == 0) {
                visit[nxt] = -color;
                result += dfs(nxt, -color);
            } else {
                if (visit[nxt] == color) {
                    result += 1;
                }
            }
        }

        return result;
    }
}