[백준 1707번] 이분 그래프 - 파이썬(python)

1707번: 이분 그래프

문제

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

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

입력

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

출력

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

풀이 설계

• 그래프가 2개로 나눠지는 이분 그래프인지를 확인해야한다.
• 먼저 그래프간의 관계를 인접리스트로 만든다.
• 이분 그래프인지 아닌지를 판별할 flag를 설정한다.
• 방문배열 visit를 만들어 BFS로 그래프가 연결을 확인한다.

풀이

• BFS로 실행

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

T = int(input())
for _ in range(T):
    V, E = map(int, input().split())
    arr = [[] for _ in range(V+1)]
    visit = [0]*(V+1)
    # 인접리스트 구하기
    for _ in range(E):
        a, b = map(int, input().split())
        arr[a].append(b)
        arr[b].append(a)
    flag = 1
    def bfs(st):
        global flag
        q= deque()
        q.append(st)
        visit[st]=1
        while q:
            now = q.popleft()
            for i in arr[now]:
                if visit[i]==0:
                    q.append(i)
                    if visit[now]==1:
                        visit[i]=2
                    elif visit[now]==2:
                        visit[i]=1
                elif visit[now]==visit[i]:
                    flag=0=

    for i in range(1, V+1):
        if visit[i]==0:
            bfs(i)

    if flag:
        print('YES')
    else:
        print('NO')

풀이2

• DFS로 실행

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

T = int(input())

def dfs(node, group):
    global flag
    visit[node] = group
    for neighbor in arr[node]:
        if visit[neighbor] == 0:
            dfs(neighbor, 3 - group)
        elif visit[node] == visit[neighbor]:
            flag = 0
            return

for _ in range(T):
    V, E = map(int, input().split())
    arr = [[] for _ in range(V + 1)]
    visit = [0] * (V + 1)
    flag = 1

    for _ in range(E):
        a, b = map(int, input().split())
        arr[a].append(b)
        arr[b].append(a)

    for i in range(1, V + 1):
        if visit[i] == 0 and flag:
            dfs(i, 1)

    if flag:
        print('YES')
    else:
        print('NO')

첫번째는 DFS, 두번째는 BFS

후기

• DFS와 BFS 두가지로 가능한 문제였다.