백준 1707번: 이분 그래프 (Python)

접근

이분 그래프가 무엇인지부터 찾아보고 이해하고 나서 쉽다고 생각했으나 생각보다 시간초과와 오래 싸웠던 것 같다.

이분 그래프란, 쉽게 말하면 모든 점을 빨강과 파랑 두가지 색으로 칠한다고 했을 때, 선으로 이어져 이웃하는 점들이 항상 서로 다른색으로 칠해질 수 있는 그래프를 말한다.

고로 한 점에서 시작하여 주어진 선들을 따라 진행하면서 이전 단계와 다른 색을 칠해주면서 탐색했을 때, 다음 칸이 이미 칠해진 같은 색을 가지고 있다면 이분 그래프가 아닌 것으로 판단해주면 된다.

코드

import sys


def bfs(a):
    q.append(a)
    visited[a] = 1
    while q:
        now = q.pop(0)
        for i in range(len(lines[now])):
            if visited[lines[now][i]] == 0:
                visited[lines[now][i]] = -1 * visited[now]
                q.append(lines[now][i])
            if visited[lines[now][i]] == visited[now]:
                return 0
    return 1


for _ in range(int(sys.stdin.readline())):
    v, e = map(int, sys.stdin.readline().split())
    lines = [[] for _ in range(v + 1)]
    for _ in range(e):
        x, y = map(int, sys.stdin.readline().split())
        lines[x].append(y)
        lines[y].append(x)
    visited = [0 for _ in range(v + 1)]
    q = []
    ans = 1
    for i in range(v):
        if visited[i] == 0:
            ans = bfs(i)
            if ans == 0:
                break
    if ans == 1:
        print('YES')
    else:
        print('NO')

더 생각해 볼 것?

처음에는 시간초과와 싸우고, 이후에는 틀렸습니다와 싸웠다. 한 점에서 시작하여 bfs 알고리즘으로 q가 없어질 때까지 탐색하면 될 줄 알았는데, 주어진 그래프가 서로 연결되지 않은(독립된) 두개의 그래프로 이루어져 있을 경우, 한점에서 출발해서는 반대쪽이 이분 그래프인지 아닌지 확인할 수 없다는 반례를 생각하기 어려웠다.

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!