[Python] 백준 1707번 '이분 그래프' (DFS/BFS)

문제

문제풀이

• 이분그래프는 같은 집합으로 들어갈 수 없어야 하므로 방문한 곳들에 특정 값 넣기
• 방문 가능하고, 이미 방문한 곳과 같은 집합에 속하지 않으면 이전 노드와 다른 값을 넣기 ( -1을 곱해주었다)
• 이전 방문한 곳과 같은 집합에 속하면 이분그래프가 아니므로 bipartite는 False
• bipartite가 True면 'YES'를 출력하고 False면 'NO'를 출력한다

코드

import sys
from collections import deque
n = int(sys.stdin.readline())
for _ in range(n):
    v,e = map(int,sys.stdin.readline().split())
    # 빈 그래프
    graph = [[] for _ in range(v + 1)]
    # 방문한 곳 저장할 배열 만들기
    visited = [0] * (v + 1)
    for _ in range(e):
        a,b = map(int,sys.stdin.readline().split())
        graph[a].append(b)
        graph[b].append(a)

    queue = deque()
    group = 1
    bipartite = True
    for i in range(1, v + 1):
        # 방문하지 않은 노드면 큐에 삽입하고
        # 같은 그룹에 속해있는지 알기 위해 그룹값을 넣어준다.
        # (여태 탐색된 노드들과 같은 그룹이 아니어야 하므로)
        if not visited[i]:
            queue.append(i)
            visited[i] = group
            while queue:
                v = queue.popleft()
                for w in graph[v]:
                    if not visited[w]:
                        queue.append(w)
                        # 방문되지 않은 노드이면 현재 노드가 가진 그룹값과 다른 값 삽입
                        visited[w] = -1 * visited[v]
                    # 같은 그룹값을 가진 방문 노드인 경우
                    elif visited[v] == visited[w]:
                        bipartite = False
    print('YES' if bipartite else 'NO')