[백준] 1707 - 이분 그래프 문제 풀이(자바,Java)

문제

1707번: 이분 그래프

들어가며

걸린 시간	2시간
성공 여부	X

 

꽤 근접하게 접근했는데 더 예외가 있을 줄은 몰랐다..

괜히 정답률 25 퍼센트 문제가 아니다.

코드

package m03.d29;

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

public class 이분_그래프_1707 {
    private static ArrayList<ArrayList<Integer>> graph;
    private static int[] color; // 0: 미방문, 1: 첫 번째 색상, 2: 두 번째 색상

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine()); // 테스트 케이스 수

        for (int i = 0; i < t; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int v = Integer.parseInt(st.nextToken()); // 정점 수
            int e = Integer.parseInt(st.nextToken()); // 간선 수

            graph = new ArrayList<>();
            for (int j = 0; j <= v; j++) { // 1-based index
                graph.add(new ArrayList<>());
            }
            color = new int[v + 1]; // 정점 번호는 1부터 시작

            for (int j = 0; j < e; j++) {
                st = new StringTokenizer(br.readLine());
                int start = Integer.parseInt(st.nextToken());
                int end = Integer.parseInt(st.nextToken());
                graph.get(start).add(end);
                graph.get(end).add(start); // 무방향 그래프
            }

            boolean isBipartite = true;

            // 모든 정점에 대해 DFS 수행 (연결 요소 처리)
            for (int j = 1; j <= v; j++) {
                if (color[j] == 0) { // 아직 방문하지 않은 경우
                    if (!dfs(j, 1)) { // 첫 번째 색상으로 시작
                        isBipartite = false;
                        break;
                    }
                }
            }

            System.out.println(isBipartite ? "YES" : "NO");
        }
    }

    private static boolean dfs(int node, int c) {
        color[node] = c; // 현재 노드에 색상 할당

        for (int neighbor : graph.get(node)) {
            if (color[neighbor] == 0) { // 아직 방문하지 않은 경우
                if (!dfs(neighbor, 3 - c)) { // 현재 색상의 반대색으로 칠함
                    return false;
                }
            } else if (color[neighbor] == color[node]) { // 인접한 노드와 같은 색이면 이분 그래프 아님
                return false;
            }
        }

        return true;
    }
}

풀이

이분 그래프의 정의가 문제에 소개 되어있다.

그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있는 그래프

 

이 말을 토대로 이분 그래프가 어떤 것인지 그려보았다.

 

"사이클"의 여부가 이분 그래프인지 아닌지에 큰 영향을 준다는 사실을 알게 되었다.

다만, 여기서도 예외가 있는데 사이클의 노드 개수가 짝수이냐 홀수이냐가 문제다.

위 그림에서 보다시피 짝수일 땐, 이분 그래프가 성립한다.

즉, 홀수 사이클을 찾아야 한다.

 

홀수 사이클을 어떻게 찾아야할까..

직관적으로 접근하는 방법 중 하나는 바로 dfs를 이용하여 인접한 노드끼리 다른 색깔을 색칠하는 방법이다.

같은 색깔은 같은 그룹인 것이다.

사실 당연한 말인게 이분 그래프는 한 그룹에 내에서 인접한 노드가 없어야 한다.

이 말은 인접한 노드는 다른 색깔을 칠하는 방식으로 완전 탐색을 하다가 같은 색깔을 만난다??

그러면 그건 이분 그래프가 아닌 것이다.

 

private static int[] color; // 0: 미방문, 1: 첫 번째 색상, 2: 두 번째 색상

이를 위해서 기존엔 visited 라는 boolean[] 배열을 사용했지만, color int[] 배열로 변경한다.

0은 미방문, 1은 첫 번째 색상, 2는 두 번째 색상을 의미한다.

private static boolean dfs(int node, int c) {
    color[node] = c; // 현재 노드에 색상 할당

    for (int neighbor : graph.get(node)) {
        if (color[neighbor] == 0) { // 아직 방문하지 않은 경우
            if (!dfs(neighbor, 3 - c)) { // 현재 색상의 반대색으로 칠함
                return false;
            }
        } else if (color[neighbor] == color[node]) { // 인접한 노드와 같은 색이면 이분 그래프 아님
            return false;
        }
    }

    return true;
}

node는 현재 노드 인덱스이고, c는 현재 노드의 색깔이다.

dfs에선 아직 방문하지 않은 인접 노드를 만났을 때, 다른 색깔을 입혀준다.

3-c 하면 다른 색깔이 나온다. (c가 1일 때, 2가 나오므로)

여기서 만약 이미 방문한 노드를 만났는데, 그 노드가 같은 색깔이라면??

그건 이분 그래프가 아니라는 의미이다.

return false르 해준다.

if (!dfs(neighbor, 3 - c)) { // 현재 색상의 반대색으로 칠함
    return false;
}

재귀문의 결과값이 false 일 경우 root로 false로 보내줘야 하니 위와 같이 작성한 것이다.

그렇게 재귀문의 최종 결과값으로 false가 전달되는 것이다.

 

boolean isBipartite = true;

// 모든 정점에 대해 DFS 수행 (연결 요소 처리)
for (int j = 1; j <= v; j++) {
    if (color[j] == 0) { // 아직 방문하지 않은 경우
        if (!dfs(j, 1)) { // 첫 번째 색상으로 시작
            isBipartite = false;
            break;
        }
    }
}

메인 함수인데 특별한 것은 없다. 같은 연결 요소가 아닌 경우도 있을 수 있으니 모든 정점에 대해 dfs를 한다.