[백준/JAVA] 1707번: 이분 그래프

🔺 문제

1707번: 이분 그래프

 

🔺 코드

import java.util.*;
import java.io.*;
 
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));
        StringTokenizer st;
        
        int K = Integer.parseInt(br.readLine());
        
        while(K --> 0) {
            st = new StringTokenizer(br.readLine(), " ");
            int V = Integer.parseInt(st.nextToken());
            int E = Integer.parseInt(st.nextToken());
            
            A = new ArrayList[V + 1];
            for(int j = 1 ; j <= V ; j++) {
                A[j] = new ArrayList<>();
            }
 
            visited = new boolean[V + 1];
            check = new int[V + 1];
            
            while(E --> 0) {
                st = new StringTokenizer(br.readLine(), " ");
                int s = Integer.parseInt(st.nextToken());
                int e = Integer.parseInt(st.nextToken());
                
                A[s].add(e);
                A[e].add(s);
            }
            
            // 🔔 모든 노드에서 수행 🔔
            isEven = true;
            for(int i = 1 ; i <= V ; i++) {
                if(isEven)  dfs(i);
                else        break;
            }
            
            System.out.println(isEven ? "YES" : "NO");
        }
    }
    
    static void dfs(int idx) {
        visited[idx] = true;
        
        for(int next : A[idx]) {
            if(!visited[next]) {
                // 인접한 노드는 같은 집합이 아니므로 이전 노드와 다른 집합으로 처리 (= 이분 그래프)
                check[next] = (check[idx] + 1) % 2;
                dfs(next);
            }
            // 🔔 이미 방문한 노드가 현재 내 노드와 같은 집합이면, 이분 그래프 X 🔔
            else if(check[idx] == check[next]) {
                isEven = false;
            }
        }
    }
}
 

✅ 해결 아이디어
✔ DFS / BFS

 

- 트리는 원래 이분 그래프임 (사이클 X)

- 자신과 반대팀 처리 : check[i] = (check[node] + 1) % 2;

 

---

🔺 다른 풀이들

- BFS 사용 & 이해하기 제일 깔끔! (인자 1개)

이분 그래프 [백준 1707][골드4][Java]

 

 

- BFS 사용 (인자 2개)

: 자신과 반대팀을 team[i] = team[node] * -1; 이렇게 -1을 곱해 처리하셨다.

[백준 - Java] 1707번 : 이분 그래프

[java 백준] 골드 4/ 1707번 이분 그래프

---

💬 느낀 점

이분 그래프 개념 혼자 이해하는 것부터 이해를 못 하였읍니다<,,,^^

다른 분들 글 보고서 그제서야 이해함,,,ㅎㅎ

뇌야 활동해라!!!

 

1회독	2회독	3회독	4회독	5회독
V	6/21