글 읽기 - python 시간초과 질문드립니다

yoodori5 3년 전 1

색칠하는 방법으로 했습니다.

노드 n개에 대하여 방문한적 없으면 bfs를 실행하도록 하여, 모든 노드에 대하여 이분 그래프 확인을 하도록 했습니다.

bicheck라는 bool 배열을 선언하여 연결된 노드끼리 True, False를 바꿔가며 저장하도록 했습니다.

만약 둘다 True이거나 False라면 이분그래프가 안되는 것이고, 바로 리턴하여 NO라고 출력합니다.

(+원래 c언어 2차원배열로 하여 메모리 초과가 떠서 append를 쓰려고 python으로 넘어왔는데 이번엔 시간초과가 뜨네요ㅠㅠ 도와주세요 고수님들...)

def bicolor(start):
    global yesno,visit,bicheck,node
    head=0
    tail=0
    q = []
    visit[start]=True
    q.append(start)
    tail=tail+1
    while(head<tail):
        now = q[head]
        for i in range(len(node[now])):
            if(visit[node[now][i]]):
                if(bicheck[now]==bicheck[node[now][i]]):
                    yesno=False
                    return
            else:
                visit[node[now][i]]=True;
                bicheck[node[now][i]]=(not(bicheck[now]))
                q.append(node[now][i])
                tail=tail+1
        head=head+1

def bfs():
    global yesno,visit
    for i in range(v):
        if(not(visit[i+1])):
            bicolor(i+1)
            if(not(yesno)):
                return

#메인함수

testcase=int(input())
for testcases in range(testcase):
    yesno=True;
    v,e=input().split()
    v=int(v)
    e=int(e)
    node = [ [] for i in range(v+1)]
    visit = [False for i in range(v+1)]
    bicheck = [False for i in range(v+1)]
    for i in range(e):
        a,b = input().split()
        a=int(a)
        b=int(b)
        node[a].append(b)
        node[b].append(a)
    bfs()
    if(yesno):
        print("YES")
    else:
        print("NO")

5ffy 3년 전 0

input()이 느려서 많은 줄의 입력을 받을때 시간초과의 주 원인이 됩니다

맨 윗줄에 아래구문을 추가해 입력을 stdin.readline으로 받아 보세요!

import sys
input = sys.stdin.readline

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

python 시간초과 질문드립니다

yoodori5 3년 전 1

5ffy 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말