1707번

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

1707번: 이분 그래프

나는 처음에 이 문제에서 주어진 이분 그래프가 뭔지 잘 이해하지 못했다.

그래서 구글링을 통해 위키백과에 정의 된 그림도 봐보고 다른 사람들의 설명도 봐보았다.

 

문제에 주어진 아래와 같은 설명은 나같은 감자에게는 이해하기 어렵다.

그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.

 

그래서 감자어로 바꾸어 보았다.

그래프의 노드를 두개의 묶음으로 나누어, 각 묶음에 속한 노드끼리는 서로 인접하지 않게 나눌 수 있으면 이분 그래프다.

즉, 시작노드와 그 인접노드는 서로 다른 묶음에 포함되어 있어야한다. ->현재의 위치에 있는 노드와 이 노드의 인접노드가 서로 다른 묶음에 있어야한다.

 

그래서 이 문제를 설명하는 것에 색깔을 도입한 글이 많아서 나도 색깔 도입을 해보았다.

출처 : 위키 백과,https://ko.wikipedia.org/wiki/이분_그래프

위의 그림은 위키 백과에서 가져온 그림이다. 그림을 보면 붉은 점과 그에 인접 점의 색이 다르고 푸른 점과 그의 인접점이 색이 다른걸 볼 수 있다.

다른 그림도 봐보자.

위 그림을 보면 붉은 점을 기준으로 보던 푸른 점을 기준으로 보던 인접한 노드의 색은 반대되는 색을 하고 있다는걸 확인할 수 있다.

이런것을 이분 그래프라고 한다. 즉, 인접한 노드의 색이 현재 노드의 색과 다르면 이분 그래프인 것이다.

 

따라서 그래프 전체에 대해서 이 조건이 성립한다면 이분 그래프인 것이다.

나는 그래서 BFS로 문제를 풀었다.

BFS의 경우에는 같은 깊이의 노드는 무조건 같은색이고, 그렇지 않으면 이분 그래프가 아닌 것이다.

즉, 현재의 노드와 인접 노드의 색이 같으면 이분 그래프가 아닌 것이다.

 

이 탐색과정에서 주의 할 것은 시작노드와 간선으로 연결되어 있지 않은 노드들이 있을 수 있으므로 탐색의 시작점 또한 반복문으로 바꾸면서 탐색하지 않은 노드가 있는지 확인해야 한다.

아래와 같은 코드로 이를 수행한다.

for(int k=1; k<=V; k++){
    if(!g.check){
        break;
    }//이분 그래프가 아니면 탐색을 종료
    if(g.colors[k]==0){
        g.bfs(k);
    }//방문하지 않은 노드에 관해 탐색
}

 

이를 통해 탐색을 시작하면, 탐색 로직인 BFS의 구현은 아래와 같다.

public void bfs(int R){
    queue.add(R);
    colors[R]=RED;
    while (!queue.isEmpty()){
        int tmp = queue.poll();
        for(int i:adj[tmp]) {
            if(colors[i]==0){
                colors[i]=colors[tmp]*-1;
                queue.add(i);
            }
            else if(colors[i]+colors[tmp]!=0){
                check=false;
                return;
            }
        }
    }
}

시작 색깔은 RED=1로 지정했다. 그리고 BLUE= -1이다.

큐에 시작 노드를 넣고 색깔 및 방문 처리 배열인 colors에 색깔과 방문을 처리하고,

큐가 빌때까지 탐색을 진행하며 큐에서 빼온 노드의 인접 노드들을 모두 탐색하면서 방문하지 않았다면 현재의 노드와 반대의 색을 넣고

방문했더라면, 현재의 노드와 탐색 하려는 인접노드의 색이 같은지 비교하여 같은 경우는 이분그래프가 아님을 표시하고 탐색을 종료한다.

 

정답코드는 아래와 같다.

package backjoon.b1707;

import java.util.LinkedList;
import java.util.Queue;
import java.util.*;
import java.io.*;
public class b1707 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int cas = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<cas; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int V = Integer.parseInt(st.nextToken());
            int E = Integer.parseInt(st.nextToken());
            Graph g = new Graph(V);
            for(int j=0; j<E; j++){
                st = new StringTokenizer(br.readLine());
                int u = Integer.parseInt(st.nextToken());
                int v = Integer.parseInt(st.nextToken());
                g.addEdge(u,v);
            }
            for(int k=1;k<=V;k++){
                if(!g.check){
                    break;
                }
                if(g.colors[k]==0){
                    g.bfs(k);
                }
            }
            if(g.check){
                sb.append("YES").append("\n");
            }
            else if(!g.check){
                sb.append("NO").append("\n");
            }
        }
        System.out.println(sb);
    }
}
class Graph{
    int node;
    int RED = 1;
    int BLUE = -1;
    LinkedList<Integer>[] adj;
    int[] colors;
    boolean check=true;
    Queue<Integer> queue;
    public Graph(int V){
        node=V;
        adj=new LinkedList[V+1];
        for(int i=0; i<=V;i++){
            adj[i]=new LinkedList<>();
        }
        colors=new int[V+1];
        queue = new LinkedList<>();
    }
    public void addEdge(int u, int v){
        adj[u].add(v);
        adj[v].add(u);
    }
    public void bfs(int R){
        queue.add(R);
        colors[R]=RED;
        while (!queue.isEmpty()){
            int tmp = queue.poll();
            for(int i:adj[tmp]) {
                if(colors[i]==0){
                    colors[i]=colors[tmp]*-1;
                    queue.add(i);
                }
                else if(colors[i]+colors[tmp]!=0){
                    check=false;
                    return;
                }
            }
        }
    }
}