글 읽기 - 시간이 너무 오래 걸리는데 혹시 어느 부분이 문제일까요?

cupyty 5년 전 0

안녕하세요. 지금 파이썬을 공부하면서 문제를 풀고 있는데요 아래 코드를 백준에 돌린 결과 성공이라고 뜨기는 하지만 약 4.6초의 시간이 소요되는 것을 볼수 있었습니다. 혹시 어떤 부분이 문제가 되어 시간이 오래 걸리는 걸까요? 많은 조언 부탁드립니다!

def bfs(g,start):
    qu=[start]
    visited=[]
    while qu:
        n=qu.pop(0)
        if n not in visited:
            visited.append(n)
        temp=g[n].copy()
        while temp:
            p=temp.pop(0)
            if p not in visited:
                qu.append(p)
    return visited
def dfs(g,start):
    stack=[start]
    visited=[]
    while stack:
        n=stack.pop()
        if n not in visited:
            visited.append(n)
        temp=g[n].copy()
        while temp:
            p=temp.pop()
            if p not in visited:
                stack.append(p)
    return visited
g={}
n,m,start = map(int,input().split())
for i in range(1,n+1):
    g[i]=[]
for i in range(m):
    a,b = map(int,input().split())
    g[a].append(b)
    g[a].sort()
    g[b].append(a)
    g[b].sort()
d=dfs(g,start)
b=bfs(g,start)
for i in d:
    print(i,end=" ")
print()
for i in b:
    print(i,end=" ")

xcm1321 5년 전 0

파이썬에서 pop(0)과 list에서의 in은 모두 O(n) 입니다. 이 부분에서 시간을 많이 잡아먹게 됩니다.

올려주신 코드의 틀을 유지하면서 바꾼 코드인데요. 채점 결과 780ms를 사용했습니다.

우선 큐를 사용해서 pop(0)을 대체했습니다.

또한 백준 파이썬 채점환경인 파이썬 3.7에서는 딕셔너리에서 삽입된 순서대로 키가 나열되어있는것이 보장되기 때문에 딕셔너리를 이용하여 방문 체크를 했습니다. 딕셔너리에서의 in은 O(1)이기 때문에 여기서도 시간을 줄일 수 있습니다.

import queue

def bfs(g,start):
    # qu=[start]
    qu = queue.Queue() # 큐로 대체
    qu.put(start)
    visited = {} # 딕셔너리로 대체
    while not qu.empty():
        n=qu.get()
        if n not in visited: # 시간복잡도 감소
            visited[n] = 1
        temp=g[n].copy()
        while temp:
            p=temp.pop(0)
            if p not in visited:
                qu.put(p)
    return visited

def dfs(g,start):
    stack=[start]
    visited={}
    while stack:
        n=stack.pop()
        if n not in visited: # 여기도 똑같습니다.
            visited[n] = 1
        temp=g[n].copy()
        while temp:
            p=temp.pop()
            if p not in visited:
                stack.append(p)
    return visited
g={}
n,m,start = map(int,input().split())
for i in range(1,n+1):
    g[i]=[]
for i in range(m):
    a,b = map(int,input().split())
    g[a].append(b)
    g[a].sort()
    g[b].append(a)
    g[b].sort()
d=dfs(g,start)
b=bfs(g,start)
for i in d:
    print(i,end=" ")
print()
for i in b.keys():
    print(i,end=" ")
print()

cupyty 5년 전 1

좋은 정보 감사합니다! 참고하면서 공부하겠습니다

nova9128 5년 전 0

앗 다른분께서 벌써 올려주셨지만 저도 도움을 드리고자 테스트를 한게 있어서

올려드립니다.

일단 가장 기본은 파이썬 입력시 input()은 굉장히 느립니다.

import sys 내의 sys.stdidn.readline 입력받으셔야 합니다.

또한 길을 찾고도 추가로 딕셔너리에 방문했던 곳을 재방문하는 반복문이어서

중간에 길을 찾으면 강제로 리턴시켰습니다.

이두가지 만으로도 시간은 988ms 까지 줄여드렸습니다.

추가로 시간 복잡도 공부하시면 더 단축하실수 있을 겁니다.

https://www.acmicpc.net/group/...

이곳 추천드립니다. 문제 유형별로 피피티 자료랑 같이 제공됩니다.

#import time
from collections import deque
import sys;s=sys.stdin.readline
def bfs(g,start,long):
    qu=deque()
    qu.append(start)
    visited=[]
    while qu:
        n=qu.popleft()
        if n not in visited:
            visited.append(n)
        temp=deque(g[n].copy())
        while temp:
            p=temp.popleft()
            if p not in visited:
                qu.append(p)
            if len(visited)==long:
                return visited
        if len(visited)==long:
            return visited
    return visited
def dfs(g,start,long):
    stack=[start]
    visited=[]
    while stack:
        n=stack.pop()
        if n not in visited:
            visited.append(n)
        temp=g[n].copy()
        while temp:
            p=temp.pop()
            if p not in visited:
                stack.append(p)
            if len(visited)==long:
                return visited
        if len(visited)==long:
            return visited
    return visited
g={}
n,m,start = map(int,s().split())
long=n
#st=time.time()
for i in range(1,n+1):
    g[i]=[]
for i in range(m):
    a,b = map(int,s().split())
    g[a].append(b)
    g[a].sort()
    g[b].append(a)
    g[b].sort()
#g[a].sort();g[b].sort()
d=dfs(g,start,long)
b=bfs(g,start,long)
#for i in d:
#    print(i,end=" ")
print(' '.join(map(str,d)))
#print()
#for i in b:
#    print(i,end=" ")
print(' '.join(map(str,b)))

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

문제

문제

출처

ICPC

시간이 너무 오래 걸리는데 혹시 어느 부분이 문제일까요?

cupyty 5년 전 0

xcm1321 5년 전 0

cupyty 5년 전 1

nova9128 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말