백준 1707 [이분 그래프]

https://www.acmicpc.net/problem/1707

from collections import deque
import sys

# with open("./data.txt", "r") as file:
#     def input():
#         return file.readline().strip()

def bfs(value):
    Q = deque()
    Q.append(value)
    colors[value] = 0
    
    while Q:
        a = Q.popleft()

        for z in maps[a]:
            
            # 첫 방문이라면 원본 노드의 반대 색상
            if(colors[z] == -1):
                Q.append(z)
                # 현재 노드가 1이면, 1-1 == 0
                # 현재 노드가 0이면, 1-0 == 1
                # 즉 현재노드와 다른 값을 가지게 할수있음
                colors[z] = 1 - colors[a]

            # 방문을 했었는데 원본 노드와 같은 색이라면
            # 인접한 노드가 같은 색이라면 이분그래프가 아님
            elif(colors[z] == colors[a]):
                return False
    
    return True

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

for _ in range(K):
    V, E = map(int, sys.stdin.readline().split(" "))

    maps = [[] for _ in range(V+1)]
    colors = [-1] * (V+1)
    
    # 인접리스트 구현
    for _ in range(E):
        u, v = map(int, sys.stdin.readline().split(" "))
        maps[u].append(v)
        maps[v].append(u)
    
    # 전체 그래프 탐색
    result = []
    for i in range(1, V+1):
        if(colors[i] == -1):
            result.append(bfs(i))
    
    if all(result):
        print("YES")
    else:
        print("NO")

이번 문제는 이분 그래프에 대한 기본 구현을 요구하는 문제였다.

모든 값이 두가지 색으로만 나뉠 수 있는 그래프가 이분 그래프라고 한다.

특징으로는

• 인접한 정점끼리는 무조건 다른 색을 가진다.
• 인접하지 않은 정점끼리는 모두 같은 색을 가진다.

위 특징을 잘 지켜서 구현을 하려고 했었는데

풀다가 현재 정점과 다른 색을 주려면 어떻게 해야하나?

고민을 하다가 막혀서 찾아보니 1 - 정점값을 해주면 됐었다.

그래서 0과 1 두가지 값으로 구분이 되게끔.

1-0 == 1
1-1 == 0

그리고 로컬에서는 정답이 나오는데 제출만 하면 1%에서 진행이 안되고 시간초과가 나길래 한참 생각하다가

input() 대신 sys.stdin.readline()을 사용하니 바로 해결이 됐다. 앞으로는 이 함수를 써야지..