강의로 돌아가기
심재훈

테스트 시간초과

테스트 1 〉 통과 (0.06ms, 10.7MB)
테스트 2 〉 통과 (0.07ms, 10.7MB)
테스트 3 〉 통과 (0.11ms, 10.8MB)
테스트 4 〉 통과 (0.88ms, 10.9MB)
테스트 5 〉 통과 (9.55ms, 12MB)
테스트 6 〉 통과 (50.44ms, 19.2MB)
테스트 7 〉 통과 (5371.85ms, 89.1MB)
테스트 8 〉 실패 (시간 초과)
테스트 9 〉 실패 (시간 초과)

이러면 뭐가 문제일까요?
최대한 속도문제 고려하고 코딩했는데 여전히 느리네요
다른 알고리즘을 써야하나요...?

작성중인 코드―solution.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
from collections import deque
def bfs2(graph, start):
    visited = []
    visited_dist = []
    dist = 0
    queue = [[start,dist]]
    queue = deque(queue)
    while queue:
        n = queue.popleft()
        if n[0] not in visited:
            visited.append(n[0])
            visited_dist.append(n[1])
            temp = graph[n[0]] - set(visited)
            for i in temp:
                queue.append([i,n[1]+1])

    return visited_dist

def solution(n, edge):
    graph = {}
    for i in range(1,n+1):
        graph[i] = set()
    for i in edge:
        graph[i[0]].add(i[1])
        graph[i[1]].add(i[0])

    last = bfs2(graph,1)
    max1 = max(last)
    answer = last.count(max1)
    return answer
  • 신현웅
    시간 복잡도와는 관련이 없지만 이게 visited 리스트를 안써야 모든 케이스에서 통과하네요.. 신현웅 2019.03.13 22:32
0 개의 답변
답변 쓰기
이 입력폼은 마크다운 문법을 지원합니다. 마크다운 가이드 를 참고하세요.