[백준] 1707: 이분 그래프 (DFS) - JAVA

알고리즘 분류 (dfs)

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

 

 

# 문제

 

 

# 필요개념

이 문제를 풀기 위해서는 이분 그래프의 개념에 대해 먼저 이해해야한다. 개념 공부를 제대로 하지 않고 접근했다가 내 정답률만 잔뜩 낮춰버렸다 😇 그래서 개념 정리겸 블로그 작성 완료 ! 아래 링크를 걸어두었다

https://wanna-developer02.tistory.com/191

[Data Structure] Bipartite Graph (이분 그래프) | 자바

 

개인적으로 길이가 짧은 코드를 좋아해서 ....... dfs로 문제를 풀었다.

 

 

# Code

import java.io.*;
import java.util.*;
public class Main {
    static List<List<Integer>> lst = new ArrayList<>();
    static int[] colors;
    static final int RED = 1;
    static final int BLUE = -1;
    static boolean isBin = true;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int test = Integer.parseInt(br.readLine());
        for (int t = 0 ; t < test ; t++) {
            isBin = true;
            StringTokenizer st = new StringTokenizer(br.readLine());
            int node = Integer.parseInt(st.nextToken());
            int edge = Integer.parseInt(st.nextToken());

            colors = new int[node + 1];
            for (int i = 0 ; i <= node ; i++) {
                lst.add(new ArrayList<>());
            }

            for (int i = 0 ; i < edge ; i++) {
                st = new StringTokenizer(br.readLine());
                int start = Integer.parseInt(st.nextToken());
                int end = Integer.parseInt(st.nextToken());
                lst.get(start).add(end);
                lst.get(end).add(start);
            }

            for (int i = 1 ; i <= node ; i++) {
                if (!isBin) break;
                if (colors[i] == 0) dfs(i, RED);
            }

            sb.append(isBin ? "YES" : "NO").append("\n");
            lst.clear();
        }
        System.out.println(sb);
    }

    private static void dfs(int start, int color) {
        colors[start] = color;
        List<Integer> child = lst.get(start);
        if (!isBin) {
            return;
        }
        for (int ch : child) {
            if (color == colors[ch]) {
                isBin = false;
                return;
            }
            if (colors[ch] == 0) {
                dfs(ch, -1 * color);
            }
        }
    }
}

 

저 isBin을 함수 밖에 생성해두고, 매 케이스마다 true로 다시 갱신해주어야 한다. 안그러면 그냥 false로 나가버린다. 이걸 못봐서 틀렸었다.

 

# 결과