99클럽 코테 스터디 9일차 TIL - 이분 그래프

문제 💁🏻‍♂️

문제 링크 - 백준 1707 이분 그래프

해결 과정

이 문제를 읽어보자마자 그래프 문제라는 감이 한번에 왔다. 그런데, 이분 그래프 라는 단어를 전공 수업 때 들어본 경험은 있지만, 정확한 내용은 알지 못했다. 이분 그래프의 정의는 다음과 같다.

인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두 가지 색으로만 칠할 수 있는 그래프

사고 과정 ❗️

이분 그래프의 정의대로 구현하기 위해서는 어떻게 하면 좋을까? 일단 하나의 정점을 시작으로 모든 정점을 파악해야한다는 점에서 DFS & BFS 알고리즘을 사용해야겠다는 생각이 들었다. 또, 하나의 정점에서부터 계속 색을 번갈아서 저장하기 때문에 DFS 알고리즘이 더 적절하다고 생각해서 DFS 알고리즘을 선택했다.

1. 시작 정점을 색깔 1로 설정하고, DFS를 실행한다.
2. 방문하지 않은 다음 노드를 방문할 때, 현재 노드의 색깔을 파악하고 만약 현재 노드의 색깔이 1이라면 다음 노드의 색깔은 2로 설정하고, DFS를 진행한다.
3. 만약, 다음 노드를 방문했다 하더라도, 현재 노드의 색깔과 같다면 이분 그래프가 아니므로 DFS 알고리즘을 종료한다.

이렇게 로직을 짜고, 코드를 짜는데 살짝 구현 부분에서 어려움을 느꼈다. 이분 그래프가 아니라는 것을 어떻게 하면 좋을까? 나는 전역으로 flag 라는 변수를 설정하고, dfs를 돌면서 이분 그래프가 아니라고 판단하면 false 처리하고 return 하도록 코드를 구현했다!

이렇게 코드를 구현하니 정답 판정을 받았다!

코드

정답 코드

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

public class Main {


    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringTokenizer st;
    static int K, V, E, u, v;
    static ArrayList<ArrayList<Integer>> vertex;
    static int[] visited;
    static boolean flag;

    public static void main(String[] args) throws IOException {

        K = Integer.parseInt(br.readLine());

        for (int tc = 1; tc <= K; tc++) {
            st = new StringTokenizer(br.readLine());
            V = Integer.parseInt(st.nextToken()); // 정점의 개수
            E = Integer.parseInt(st.nextToken()); // 간선의 개수

            vertex = new ArrayList<>();
            for (int i = 0; i <= V; i++) {
                vertex.add(new ArrayList<Integer>());
            }

            for (int i = 0; i < E; i++) {
                st = new StringTokenizer(br.readLine());
                u = Integer.parseInt(st.nextToken());
                v = Integer.parseInt(st.nextToken());
                // 양방향 간선
                vertex.get(v).add(u);
                vertex.get(u).add(v);
            }

            visited = new int[V + 1];
            flag = true;
            for (int i = 1; i <= V; i++)
                // 방문한 적이 없다면 -> 방문
                if (visited[i] == 0) {
                    visited[i] = 1; // 1로 색칠
                    dfs(i);
                }
            if (flag) bw.write("YES\n");
            else bw.write("NO\n");
        }

        bw.close();
    }

    private static void dfs(int curr) {

        for (int i = 0; i < vertex.get(curr).size(); i++) {
            int nxt = vertex.get(curr).get(i);
            // 다음 노드를 방문한 적이 없는 경우
            if (visited[nxt] == 0) {
                // 현재 색이 1인 경우
                if (visited[curr] == 1) {
                    visited[nxt] = 2; // 2로 색칠
                    dfs(nxt);
                } else {
                    visited[nxt] = 1; // 1로 색칠
                    dfs(nxt);
                }
            }
            // 현재 노드가 다음 노드와 색이 같다면 -> 이분 그래프가 아니다.
            else if ((visited[curr] + visited[nxt]) % 2 == 0) {
                flag = false;
                return;
            }
        }
    }
}

Reference

• https://gmlwjd9405.github.io/2018/08/23/algorithm-bipartite-graph.html