백준 1707 python 풀이 (이분 그래프, BFS)

일단 처음에 문제를 읽고는 생각보다 쉽다고 느꼈다. 단순히 BFS로 탐색하면서 이전 값이랑 비교하면 되겠구만 했다. 그런데 구현하는데 상당히 애를 먹었고, 시간초과가 떠서 오랜 삽질 중이다.

우선 시간초과 코드는 아래와 같다.

from collections import deque
import sys
input = sys.stdin.readline
T = int(input())

def BFS(v,e,color, d,q):
    color[q[0]] = 1
    visited = [0 for i in range(v+1)]
    while q:
        target = q.popleft()
        visited[target] = 1
        targets = d[target]
        for t in targets:
            if visited[t] == 0:
                q.append(t)
            else:
                continue
            if color[t] == -1: #안칠해짐
                color[t] = color[target]^1
            else: #이미 칠해짐
                if color[t] == color[target]:#이분 그래프 아님
                    return "NO"
    return "YES"

for _ in range(T):
    v,e = map(int, input().split())
    d = {}
    color = [-1 for i in range(v+1)]
    q = deque([])
    for i in range(e):
        tmp=list(map(int,input().split()))
        if i == 0:
            q.append(tmp[0])
        if tmp[0] not in d: # 없는경우
            d[tmp[0]] = [tmp[1]]
        else:
            d[tmp[0]].append(tmp[1])
        if tmp[1] not in d:
            d[tmp[1]] = [tmp[0]]
        else:
            d[tmp[1]].append(tmp[0])
    print(BFS(v,e,color, d, q))

 

그래서! 고수의 코드를 쓱 훔쳐보고 와서 다시 코딩을 진행했다.

기존의 코드는 dictionary에 값을 넣고 하나씩 방문하며 visited와 color배열을 돌며 검증을 한다. 문제는 dictionary에 넣는 과정에서 매번 dictinary의 key값들을 돌며 확인하기 때문에 시간복잡도가 오래 걸린다.

그러나 새로운 코드는 배열에 값들을 빠르게 집어넣고 첫 노드부터 방문하여 이분 그래프인지 확인한다.

따라서 BFS의 내부 로직은 비슷하지만 초기에 그래프를 세팅하는 과정에서 속도 차이가 많이 나는듯 하다.

구현한 코드는 아래와 같다.

from collections import deque
import sys
input = sys.stdin.readline
T = int(input())

def BFS(Map, target, visited):
    visited[target] = 1
    q = deque([target])
    while q:
        target = q.popleft()
        targets = Map[target]
        for t in targets:
            if visited[t] == 0: #방문 x
                visited[t] = -visited[target]
                q.append(t)
            else: #방문 했으면 비교
                if visited[t] == visited[target]:#이분 그래프 아님
                    return "NO"
    return "YES"
for _ in range(T):
    v,e = map(int, input().split())
    Map = [[] for i in range(v+1)]
    visited = [0  for i in range(v+1)]
    for i in range(e):
        a,b=map(int,input().split())
        Map[a].append(b)
        Map[b].append(a)
    flag = True
    for i in range(1,v+1):
        if visited[i] == 0:
            if BFS(Map, i, visited) == "NO":
                flag = False
                break
    if flag == True:
        print("YES")
    else:
        print("NO")

결론은 그래프를 초기에 어떻게 세팅하는지 얼마나 빠르게 세팅하는지도 굉장히 중요하다.