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

문제

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

완전탐색 활용 문제 너무 어려워..! 근데 구현 아이디어를 알고 나니까 코드 짜는 건 좀 재밌었다

풀이

🥹 처음 아이디어

노드를 두 그룹으로 나눌 때, 같은 그룹 끼리는 간선이 없어야 함 

이 개념만 가지고 노드를 두 그룹으로 어떻게 나눠야 할까 생각했다.

 

1. 간선이 있으면 다른 그룹으로 나누는 작업을 반복 -> 끝까지 진행 후 총 2그룹이면 YES
  -> 고민: 같은 그룹인지 어떻게 구분함..? 

  -> 그룹이 뭔지 저장하는 group[v+1]을 만들고 노드 1부터 순차 탐색, 인접하지 않은 노드를 발견하면 다 같은 그룹으로 표시하기
  -> 근데 이 방법은 시간 복잡도가 O(V^2)이기 때문에 틀린 풀이 (제한 시간 2초, V<=20,000)

2. 단, 어떤 그룹에 넣기 전에 그 그룹에 이미 속한 다른 노드들과 인접한지 확인 -> 인접하지 않으면 넣기

3. 그룹 수가 3개 이상이 되면 탐색 종료하고 NO 출력

 

💡옳은 풀이

노드를 두 그룹으로 분리하기 위해 R 또는 B를 색칠한다.

노드x를 R로 색칠했다면 노드x와 인접한 모든 노드들은 다른 그룹에 속해야 하므로 B를 칠해야 한다.

 

이 과정을 BFS 탐색을 하면서 반복한다.

여기서 색을 칠하는 행위를 방문 체크로 취급할 수 있기 때문에 방문 체크 배열 이름을 colors로 만들고 

색칠했으면 어떤 색을 칠했는지 해당 노드와 일치하는 인덱스에 넣어주면 된다. 

(그룹을 두 개로만 표현하면 되므로 나는 두 색을 1, -1로 표시했다. 현재 노드 색과 다른 색을 넣어줄 때 현재 노드 색에 음수처리만 해주면 됨)

 

큐에 아무 노드나 하나 넣고 방문 체크로 colors에 아무 색이나 하나 집어넣음 (1을 넣었음)

큐가 빌 때까지 수행 :

큐에서 노드 하나 꺼내고 그 인접 노드들을 탐색한다.

-> 인접 노드를 아직 방문하지 않았다면 즉 색칠하지 않았다면 (colors값이 0) 아까 꺼낸 노드랑 다른 색을 넣어주고 큐에 인접 노드 넣기

-> 인접 노드의 색이 큐에서 꺼낸 노드와 같다면 이분 그래프가 아니므로 더 탐색할 필요 없음. 바로 BFS를 멈추고 return false

 

주의할 점은 그래프가 두 개로 나뉘어져있을 수 있음

BFS는 그래프 한 개 단위로 완전 탐색하므로 아직 방문하지 않은 모든 노드에 대해 BFS를 수행하게 해야 한다.

 

 

 

 

 

코드

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

public class Main {
    static int v, e;
    static List<List<Integer>> graph;
    static int[] color;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int tc = Integer.parseInt(br.readLine());
        for(int t=0; t<tc; t++){
            st = new StringTokenizer(br.readLine());
            v = Integer.parseInt(st.nextToken());
            e = Integer.parseInt(st.nextToken());

            graph = new ArrayList<>();
            for(int i=0; i<v+1; i++){
                graph.add(new ArrayList<>());
            }

            for(int i=0; i<e; i++){
                st = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                graph.get(x).add(y);
                graph.get(y).add(x);
            }

            color = new int[v+1];

            boolean isBiGraph = true;
            for(int i=1; i<v+1; i++){
                if(color[i]==0){ //아직 방문하지 않은 모든 노드에 대해 bfs를 수행해야 떨어져 있는 그래프도 확인됨
                    if(!bfs(new Node(i, 1))){
                        isBiGraph = false;
                        break;
                    }
                }
            }
            if(isBiGraph){
                System.out.println("YES");
            }else{
                System.out.println("NO");
            }

        }
    }
    static boolean bfs(Node node){
        Queue<Node> q = new LinkedList<>();
        q.add(node);
        color[node.num] = 1;

        while(!q.isEmpty()){
            Node now = q.poll();
            List<Integer> nexts = graph.get(now.num);
            for(int next: nexts){
                if(color[next]==now.color)
                    return false;
                else if(color[next]==0){
                    q.add(new Node(next, -now.color));
                    color[next] = -now.color;
                }
            }
        }
        return true;
    }
}

class Node{
    int num, color;
    Node(int num, int color){
        this.num = num;
        this.color = color;
    }
}