99클럽 코테 스터디 9일차 TIL Boj 1707. 이분 그래프

Approach

• 문제 이해를 잘못해서, 집합을 나누고 서로 색깔이 달라야하는 줄 알았는데, 단순히 인접한 노드가 서로 색깔이 다르면 되는 문제였다.
• 이분 그래프가 아니어서 No여도 밖에서 break문을 걸어주지 않는다면 , 후에 탐색할 때 YES인 그래프도 나올 수 있다는 것을 알았다. (출력 형식이 잘못됨)

---

Solution 💡

import sys
from collections import deque

def bfs(start):

    queue = deque()
    queue.append(start)
    visited[start] = 1

    while queue:
        node = queue.popleft()

        for next in graph[node]:
            if not visited[next]:
                visited[next] = -visited[node]
                queue.append(next)
            
            elif visited[node] == visited[next]:
                return False
    
    return True

K = int(sys.stdin.readline().strip())

for _ in range(K):
    V, E = map(int, sys.stdin.readline().split())
    graph = [[] * (V+1) for _ in range(V+1)]
    for _ in range(E):
        a, b = map(int, sys.stdin.readline().split())
        graph[a].append(b)
        graph[b].append(a)

    answer = True
    visited = [0] * (V+1)
    for i in range(1, V+1):
        if not visited[i]:
            answer = bfs(i)

        if not answer:
            print("NO")
            break
    
    else:
        print("YES")