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

문제

이분 그래프 문제 링크

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

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

입력

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

2
3 2
1 3
2 3
4 4
1 2
2 3
3 4
4 2

출력

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

YES
NO

접근 방식

• 이분 그래프의 특징은 각 정점과, 연결된 다른 정점은 색이 달라야 한다는 것이다

• 깊이 우선탐색으로 정점을 방문할 때마다 color라는 변수를 둬 1 또는 -1 로 방문 표시를 한다 (방문을 안했다면 0)

• 방문한 정점일 때 현재 정점과 다른 color이면 옳은 것 이므로 pass 하고 아니라면 global 변수인 answer를 "NO" 로 바꾼다

• 모든 정점에 대해 검사하여 비연결 그래프에서 그래프 중 하나라도 이분 그래프가 아닐 시 answer는 "NO"를 가진다

코드

# url : https://www.acmicpc.net/problem/1707
# 난이도 : gold 4

import sys
sys.setrecursionlimit(10**6) # 백준 재귀제한 해제

tc = int(input())

# 변형한 dfs
def dfs(node,color):

    global answer
	
    # 방문 시 표시를 color로 표현 
    # visited리스트의 각 값은 -1,0,1 중 하나
    visited[node] = color
    for i in graph[node]:
        if visited[i] == 0 :
        # 방문하지 않았다면 -color를 주어 색을 바꿈
            dfs(i,-color)
        elif visited[i] == -color:
            pass
        else:
            answer = "NO"
            return


for _ in range(tc):
    V,E = map(int,sys.stdin.readline().split())

    graph = [[] for _ in range(V)]
    answer = "YES"
    for _ in range(E):
        u,v = map(int,sys.stdin.readline().split())

        graph[u-1].append(v-1)
        graph[v-1].append(u-1)

    visited = [0] * V

    for i in range(V):
        if visited[i] == 0 : 
            dfs(i,1)

    print(answer)