백준 풀이

이분 그래프

정점들이 두 그룹으로 나뉜다는 개념을 정확히 이해하지 못했다.

'두 그룹으로 나뉜다' 라는 부분에서 '두 정점이 맞닿을 때 두 정점은 항상 서로다른 그룹이다' 라고 이해하는 편이 더 낫겠다고 생각했다.

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)


def bipartite_graph_with_dfs(now):
    global graph, colors, is_bipartite

    for next in graph[now]:
        # 다음 노드의 색이 현재 노드의 색깔과 같을 경우 flag세팅 후 종료
        if colors[now] == colors[next]:
            is_bipartite = False
            return
        
        # 방문하지 않았다면 색을 지정하고 방문한다.
        if colors[next] == 0:
            colors[next] = -colors[now]
            bipartite_graph_with_dfs(next)
    return


K = int(input())
for _ in range(K):
    V, E = map(int, input().split())
    graph = dict((node, []) for node in range(1, V+1))
    # color: 1, -1 두가지 / 0이면 방문하지 않은 노드
    colors = [0, 1] + [0] * (V-1)
    is_bipartite = True

    # input
    for _ in range(E):
        u, v = map(int, input().split())
        graph[u].append(v)
        graph[v].append(u)

    # main
    for i in range(1, V+1):
        bipartite_graph_with_dfs(i)
    # print(f'colors: {colors}')
    if is_bipartite:
        print('YES')
    else:
        print('NO')

내가 현재 위치한 노드에서 다음 노드로 탐색하기 전에 서로 다른 그룹인지 확인하는 과정을 거쳤다.

color를 활용해서 -1, 1 값을 두 그룹으로 설정했고, 0이면 아직 방문하지 않았다고 설정하고 진행했다.