[파이썬, Java] 1707. 이분 그래프

문제

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

그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호 u, v (u ≠ v)가 빈 칸을 사이에 두고 주어진다. 

출력

K개의 줄에 걸쳐 입력으로 주어진 그래프가 이분 그래프이면 YES, 아니면 NO를 순서대로 출력한다.

제한

• 2 ≤ K ≤ 5
• 1 ≤ V ≤ 20,000
• 1 ≤ E ≤ 200,000

예제 입력 1 

2

3 2

1 3

2 3

4 4

1 2

2 3

3 4

4 2

예제 출력 1 

YES

NO

 

 

🐍 나의 풀이

from collections import deque
import sys
input=sys.stdin.readline
K=int(input())      # 테스트 케이스의 개수


def bfs(i, num) :
    global ans
    que=deque([i])
    visit[i]=num

    while que :
        node=que.popleft()
        for v in graph[node] :
            if not visit[v] :
                que.append(v)
                visit[v]=visit[node]*-1
            elif visit[v]+visit[node] != 0 :	# 1+1 또는 -1+-1일 경우
                ans=0
                return


for _ in range(K) :
    ans=1
    V, E=map(int, input().split())      # 정점의 개수, 간선의 개수
    graph=[list() for _ in range(V+1)]
    visit=[0]*(V+1)     # 1과 -1로 그룹을 구분
    for e in range(E) :
        a, b=map(int, input().split())
        # 양방향 연결
        graph[a].append(b)
        graph[b].append(a)

    for i in range(1, V+1) :
        if not ans :
            break
        if not visit[i] :
            bfs(i, 1)

    if not ans :
        print("NO")
    else :
        print("YES")

다른 사람의 자바 풀이를 참고했다.

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

이 문제는 bfs가 적합하다.

아이디어를 떠올리는 게 쉽지 않겠지만, 구현은 어렵지 않다.

어떤 정점 node와 연결된 정점 v들이 서로 다른 집합인지 확인하면 된다.

이것을 1 또는 -1로 나누어 구분했다.

만약 어떤 node가 1에 속하는데 연결된 정점 중 어떤 v가 똑같이 1이면 이분 그래프가 아니다.

 

 

🦔 다른 사람 풀이

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

public class Main{
    static class Node{
        int to;
        Node link;

        public Node(int to, Node link){
            this.to=to;
            this.link=link;
        }
    }

    static int[] vertex;
    static Node[] graph;

    public static void main(String[] args) throws Exception{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int testcase=Integer.parseInt(br.readLine());

        LOOP : for(int t=1; t<=testcase; t++){
            StringTokenizer st=new StringTokenizer(br.readLine());
            int v=Integer.parseInt(st.nextToken());
            int e=Integer.parseInt(st.nextToken());
            vertex=new int[v+1];
            graph=new Node[v+1];

            for(int i=0; i<e; i++){
                st=new StringTokenizer(br.readLine());
                int from=Integer.parseInt(st.nextToken());
                int to=Integer.parseInt(st.nextToken());

                graph[from]=new Node(to, graph[from]);
                graph[to]=new Node(from, graph[to]);
            }

            for(int i=1; i<v+1; i++){
                if(vertex[i] != 0)
                    continue;

                vertex[i]=1;
                if(!dfs(i, 1)){
                    System.out.println("NO");
                    continue LOOP;
                }
            }
            System.out.println("YES");
        }
    }

    public static boolean dfs(int i, int num) {
        for(Node cur=graph[i]; cur != null; cur=cur.link){
            int to=cur.to;

            if(vertex[to] != 0 && vertex[to] == num)
                return false;

            if(vertex[to] == 0){
                vertex[to]=-num;
                if(!dfs(to, -num)){
                    return false;
                }
            }
        }
        return true;
    }
}

dfs로 구현

방문 하지 않은 정점 i를 대상으로 연결 된 노드를 dfs로 탐색한다.

 

 

문제 출처 👉 백준