boj.kr/1707 이분 그래프 (gold4) 파이썬 풀이

시작노드를 인덱스로 하고 인접노드를 요소로 갖는 1. graph 리스트와

이분 그래프 여부를 판단하는 2. 플래그 변수를 사용한 풀이이다.

3. sys.stdin.readline 으로 빠른 입력 받기를 사용해야 시간초과 나지 않는다.

 

 

풀이1 - DFS 활용

import sys
sys.setrecursionlimit(10**6)
N = int(input())

input = sys.stdin.readline
def dfs(node):
    global flag
    for neighbor in graph[node]:
        if (visited[neighbor] == -1):
            visited[neighbor] = 1 if (visited[node] == 2) else 2
            dfs(neighbor)
        else:
            if visited[node] == visited[neighbor]:
                flag = False
                return


for _ in range(N):
    flag = True
    V, E = map(int, input().split())
    visited = [-1] *(V+1)
    graph = [[] for _ in range(V+1)]
    for _ in range(E):
        start, end = map(int, input().split())
        graph[start].append(end)
        graph[end].append(start)

    for i in range(1, V+1):
        if (visited[i] == -1):
            visited[i] = 1
            dfs(i)
            if (flag == False):
                break

    print("YES" if flag else "NO")

 

풀이2 - BFS 활용

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

def bfs(node):
    dq = deque()
    dq.append(node)
    while dq:
        cur = dq.popleft()
        for nxt in graph[cur]:
            if visited[nxt] == -1:
                visited[nxt] = 1 if visited[cur] == 2 else 2
                dq.append(nxt)
            elif visited[nxt] == visited[cur]:
                return False
    return True

T = int(input())
for _ in range(T):
    V, E = map(int, input().split())
    graph = [[] for _ in range(V+1)]
    for _ in range(E):
        s, e = map(int, input().split())
        graph[s].append(e)
        graph[e].append(s)
    visited = [-1 for _ in range(V+1)]
    flag = True
    for node in range(1, V+1):
        if visited[node] == -1:
            if not bfs(node):
                flag = False

    print("YES" if flag else "NO")