이분 그래프 [백준 1707]

1. 문제 접근 방법

- 이분 그래프가 가능한지 묻는 문제이다.

   이분 그래프가 가능한지 판단하기 위해서, 방문하는 점마다 1, 2를 번갈아가면서 컬러링을 하고,

   만약에 이웃하는데 같은 색깔을 컬러링해야 한다면, 

   이분 그래프를 만드는 것이 불가능하므로, "NO"가 된다고 해주면 된다.  

 

 

2. 코드

from collections import deque


K = int(input())


def bfs(start, edge, visited):
    
    
    q = deque()
    ## 현재 점의 색깔을 1으로 하고, 
    ## 다음 점을 탐색한다. 
    q.append((start, 1))
    
    ## 방문한 점에는 색깔을 칠해준다. 
    visited[start] = 1
    
    
    while q:
        
        num, color = q.popleft()
        
        
        for next in edge[num]:
            ## 방문하지 않은 점이라면, 
            ## 현재 점이 색깔이 1이라면, 2를 칠하고,
            ## 색깔이 2라면, 1을 칠한다. 즉, 반대 색깔을 칠해준다. 
            if visited[next] == 0:
                if color == 1:
                    visited[next] = 2
                    q.append((next, 2))
                else:
                    visited[next] = 1
                    q.append((next, 1))
            else:
            ## 방문한 점이라면, 현재 점의 색깔과 다음 점의 색깔이 같으면
            ## 이분 그래프가 불가능하므로, False를 리턴한다. 
                if color == 1:
                    if visited[next] == 2:
                        continue
                    else:
                        return False
                if color == 2:
                    if visited[next] == 1:
                        continue
                    else:
                        return False
    
    
    
    return True 
    
    



for i in range(K):
    
    ## V, E를 입력 받는다
    ## V는 정점의 개수, E는 간선의 개수를 의미한다. 
    V, E = map(int, input().split())
    edge = [[] for _ in range(V+1)]
    
    ## 간선의 정보를 edge 배열에 저장한다.
    ## 이 때, 양방향으로 edge 배열에 저장한다. 
    for j in range(E):
        u, v = map(int, input().split())
        edge[u].append(v)
        edge[v].append(u)
        
    ## visited 배열을 만들고 0으로 초기화한다.      
    visited = [0]*(V+1)
    
    ans = "YES"
    
    ## 1번 노드부터 V번 노드까지 순차적으로 탐색한다. 
    ## 단, 이 때 방문하지 않은 노드들을 탐색한다
    ## 탐색은 BFS로 한다. 
    ## 이렇게 해야 하는 이유는 고립된 정점이 있을 수도 있으므로,
    ## 이렇게 해야 모든 정점에 대한 탐색이 가능하기 때문이다. 
    for j in range(1, V+1):
        if visited[j] == 0:
            res = bfs(j, edge, visited)
            
            ## 하나라도 False가 존재한다면 ans는 NO가 된다. 
            if res == False:
                ans = "NO"
                
    print(ans)