글 읽기 - DFS) Python 시간초과

yechance 4년 전 0

같은 코드를 C++로 작성했을때는 통과하는데, 파이썬은 시간 초과가 납니다..
진짜 일반적인 dfs를 구현했고,, 파이썬은 전역변수 사용이 저는 까다로워서 그냥 클래스로 만들어서 멤버변수에 접근하는 식으로 구현했는데

느립니다... 속도를 올리는 방법이 있을까요?

DFS 구현시 스택과 재귀의 속도차이는 얼마나 나나요??ㅠㅠㅠ

class graph(object):
    # 초기화 할때 인접리스트 정보를 초기화
    def __init__(self, adj):
        self.n = len(adj)
        self.adj = adj
        self.visited = []
    
    # 일반적인 스택으로 구현한 dfs
    def dfs(self, here):
        stack = [here]
        while stack:
            top = stack.pop()
            self.visited[top] = True
            for v in self.adj[top]:
                if not self.visited[v]:
                    stack.append(v)
        return
    
    # dfs의 호출하는 수로 컴포넌트의 수를 구함
    def dfsAll(self):
        self.visited = [False] * self.n
        count = 0
        for i in self.adj.keys():
            if not self.visited[i]:
                self.dfs(i)
                count += 1
        return count

# 입력 N: 정점수  M: 간선수
N, M = list(map(int, input().split(" ")))

# 딕셔너리로 그래프 인접리스트 구현
d = {}
# 간선 입력값 인접리스트에 저장
for _ in range(M):
    v1, v2 = list(map(lambda a: int(a)-1, input().split(" ")))
    d[v1] = d.get(v1, []) + [v2]
    d[v2] = d.get(v2, []) + [v1]
# graph 클래스
g = graph(d)

print(g.dfsAll())

sait2000 4년 전 2

1000개짜리 완전그래프가 들어오면 첫 번째 노드를 볼 때 나머지를 다 stack에 넣은 다음, 두 번째 노드를 볼 때 또 나머지를 (거의) 다 다시 스택에 넣게 됩니다. 세 번째 노드를 볼때도 마찬가지로요. 그럼 스택의 길이가 대략 n^2/2즈음까지 커집니다. 스택의 각각의 원소에 대해 O(n)의 시간이 걸리니까 O(n^3)이 될 거 같네요.

그리고 input보다 sys.stdin.readline을 쓰면 입력이 좀 빨라집니다.

그리고 37번 줄 38번 줄은.. 별로 빠를 거 같진 않네요 append를 써보시죠.

wjsqjawns 4년 전 1

입력 방법을 바꿉니다. (readline 등을 사용)
중복을 줄입니다. (16번째 줄에서 stack에 v를 넣을 때 v에 대한 방문 여부를 True로 바꿔주는 방법 등)

위의 두 가지를 처리해주시면 시간 초과는 해결됩니다.

yechance 4년 전 2

sait2000님, wjsqjawns님 답변 감사드려요ㅠㅠㅠ
두분의 답글 보니까 그냥 명확하게 이해되어버렸어요ㅠㅠ
제 코드에서 스택에 집어넣을때 방문표시를 하는것과 입력방법을 쫌 바꾸면 되는 걸 알았어요!!ㅎㅎㅎ
시간복잡도는 자꾸 자세히는 못보게 되는데 고려해야하는걸 많이 느끼네요 ㅠㅠㅠ
그렇게 도움주셔서 감사합니다!! 좋은 하루 보내세욯ㅎㅎ

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

문제

문제

출처

ICPC

DFS) Python 시간초과

yechance 4년 전 0

sait2000 4년 전 2

wjsqjawns 4년 전 1

yechance 4년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말