[백준] [파이썬] [Graph] 1707번: 이분 그래프

문제집 추천, 이 문제집에 나온 유형들만 공부해도 코딩테스트는 거뜬: https://www.acmicpc.net/workbook/by/BaaaaaaaaaaarkingDog

 

1707번: 이분 그래프 문제 보러 가기

제한시간: 2초
메모리 제한: 256 MB

문제

그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (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

---

진짜 문제가 불친절하다. 예시도 적고 문제도 뭔소리인지... 이해하기 힘들다.

 

우선 이분 그래프가 무엇인지 문제를 이해해보자.

 

이분 그래프: 집합이 두 개 있을 때, 인접한 노드끼리 서로 다른 집합에 넣을 수 있다면 이분 그래프이다.
-> 일단 이것부터 무슨 소리인지 이해하기 힘들다.

 

이분 그래프인 경우 : 인접한 노드끼리 서로 다른 집합에 들어가게 만들 수 있으면 이분 그래프이다.
(같은 집합은 같은 색으로 표시했음)

 

 

이분 그래프가 아닌 경우:

 

 

즉, 각 노드들을 이웃 노드들과 다른 색으로 칠해 나가는데, 이웃 노드끼리 같은 색을 갖고 있으면 이분 그래프가 아니고 

이웃 노드끼리 서로 다른 색으로 칠 할 수 있으면 그건 이분 그래프 이다.

 

이 문제는 같은 색깔의 노드가 서로 연결되어 있는 모순이 발생하는지 여부를 확인하는 문제이다. 또는 사이클 여부를 확인하는 문제이기도 하다.

 

그렇다면 어떻게 색을 칠 할 수 있을까? 색은 2종류밖에 없다. 

visited =[0]*(N+1)을 이용해서 색을 칠한다. 예를 들어 예제 입력 1에서 

3 2
1 3
2 3

인 경우 

 

visited=[0,1,1,-1] 로 표현하면 노드 1은 색이 1, 노드 2는 색이 1, 노드 3은 색이 -1로 인접한 노드끼리 색이 다르다. 

이 개념으로 현재 노드에 붙어 있는 노드에 다른 색을 부여하고 같은 색이 되면 False를 추출하는 방식으로 코드를 짜보자.

 

---

BFS로 푼 정답 코드 

import sys
from collections import deque
input = sys.stdin.readline

def BFS(s,g):       # start node, group
    Q=deque()
    Q.append(s)
    visited[s]=g
    while Q:
        x=Q.popleft()
        for n in graph[x]:
            if visited[n]==0:
                visited[n] = visited[x]*-1      # 상위 노드와 다른 그룹으로 편성하기 위해, 색을 칠한다, 색은 딱 2개 
                Q.append(n)
            elif visited[n]==visited[x]:        # 상위 노드가 현재 노드와 같은 그룹이면
                return False                    # 서로 이웃한 노드가 붙어있다는 뜻 
    return True     # 무사히 while문에 벗어나서 (위 조건에 걸리지 않아서) True 리턴

if __name__=="__main__":
    K=int(input())
    for _ in range(K):
        V,E=map(int, input().split())       # V:노드 개수, E:간선 개수 
        graph=[[] for _ in range(V+1)]
        visited=[0]*(V+1)
        
        for _ 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 visited[i]==0:
                res=BFS(i,1)    # 현재 노드를 살펴보고 이분 그래프인지 아닌지 확인 
                if not res:     # 현재 노드에서 같은 색의 이웃한 노드가 발견되면 
                    break       # 이분 그래프 아님
        
        if res:
            print('YES')
        else:
            print('NO')

은근 이전 그래프 문제와 유사하다. elif가 있고 방문하면 방문 표시로 1을 만들어주기만 했는데 이번에는 두개의 그룹으로 1 또는 -1을 해야한다는 점이 다르긴 하지만.

 

---

DFS로 푼 정답 코드 

 

주의할 점 :

1. 1번 노드에 대해서만 DFS를 진행해서는 안된다. 주어진 그래프가 연결 그래프라는 보장이 없기 때문이다.

2. 입력 데이터가 많기 때문에, 파이썬으로 코드를 제출할 경우 반드시 sys.stdin.realine()을 활용 해야한다.

3. setrecursionlimit 으로 재귀 함수 호출 리밋을 해제해줘야 한다.

4. pypy로 제출할 경우 메모리 초과가 나지만, python3로 제출할 경우 통과한다.......

 

 

import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline

def DFS(s,g):       # start node, group
    visited[s]=g
    for n in graph[s]:
        if visited[n]==0:
            res=DFS(n,-g)
            if not res:
                return False
        elif visited[n]==visited[s]:
            return False
    return True

if __name__=="__main__":
    K=int(input())
    for _ in range(K):
        V,E=map(int, input().split())       # V:노드 개수, E:간선 개수 
        graph=[[] for _ in range(V+1)]
        visited=[0]*(V+1)
        
        for _ 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 visited[i]==0:
                res=DFS(i,1)
                if not res:
                    break
        
        if res:
            print('YES')
        else:
            print('NO')

---

기존 그래프 문제랑 비슷하게 진행 되는데 1과 -1 개념 추가는 색달랐다. 역시 문제를 많이, 다양히 풀어봐야한다.