글 읽기 - dfs 시간초과 문제입니다 ㅠㅠ

bunggl 4년 전 0

플로이드 와샬 말고 dfs/bfs 로 풀고싶어서 dfs로 풀고 있는데
시간 초과가 계속 걸리네요.. 어떻게 시간 단축을 할 수 있을까요?

from sys import stdin
def sol():
    answer = list()
    n,k = map(int,stdin.readline()[:-1].split())
    graph = dict()
    check = dict() 
    for i in range(k):
        p, l = map(int,stdin.readline()[:-1].split())
        if(p in graph.keys()):
            graph[p].append(l)
        else:
            graph[p] = [l]
    visit = dict()
    for i in range(1, n+1):
        visit[i] = 0
        if(i in graph.keys()):
            check[i] = 1
        else: 
            check[i] = 0  
    t = int(stdin.readline()[:-1])
    i =0
    while(i<t):
        p, l = map(int,stdin.readline().rstrip().split())
        answer.append(dfs(p,l,graph,visit,check))
        i+=1
    for item in answer:
        print(item)
def dfs(p,l,graph,visit_p,check):
        visit = visit_p
        stack = list()
        stack.append(p)
        while(stack): #stack -> node -> graph -> node
            node = stack.pop()
            if(visit[node] == 0): 
                if(node == l):
                    return -1 
                else: 
                    if(check[node] == 1):
                        stack.extend(graph[node])  
                visit[node]=1 
                    
        stack.append(l)
        n = len(visit.keys())
        for i in range(1, n+1):
            visit[i] = 0
        while(stack):
            node = stack.pop()
            if(visit[node] == 0): 
                if(node == p):
                    return 1 
                else:
                    if(check[node] == 1):
                        stack.extend(graph[node])
                visit[node]=1 
        return 0
if __name__=='__main__':
    sol()

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

문제

문제

출처

ICPC

dfs 시간초과 문제입니다 ㅠㅠ

bunggl 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말