글 읽기 - [python 3] 11724 시간초과 해결법

choah76 3년 전 0

이 문제를 풀기 위해 구상한 알고리즘은 다음과 같습니다.

1. 1~N의 숫자가 있는 list를 만들고, 그래프의 L[0]번( =1번) 정점에서 bfs를 시작한다.

2. bfs리턴값으로 방문한 지점들이 list로 나온다 (ex : vis = [1,2,3,4,5])

3. 1-N의 숫자가 있는 list에서 vis의 원소들을 제거한다.

4. 다시 L[0]번 정점에서 bfs를 시작한다.

5. 이 반복한 횟수가 곧 연결요소의 개수이다.

그러나 자꾸 시간초과가 뜹니다. 개선점을 알려주시면 감사하겠습니다.

N = list(map(int,input().split()))
 #변수 및 리스트 설정
L = []
graph = {}
N0 = N[0]
N1 = N[1]


#인접 리스트 구현
for i in range(N0) :
    L.append([])


for i in range(N1) :
    a,b = map(int, input().split())
    L[a-1].append(b)
    L[b-1].append(a)

# 친구관계 그래프 표현
k = 1
for item in L :
    item.sort()
    graph[k] = item
    k += 1

from collections import deque

def bfs(graph, start) :
    vis = []
    stack = deque(range(start,start+1))

    while stack :
        n = stack.popleft()
        if n not in vis :
            vis.append(n)
            G = graph[n] # n정점과 연결된 정점들
            V = list(set(vis)) # vis 중복원소 제거
            for item in G :
                if V.count(item) >= 1:
                    pass
                else :
                    stack.append(item)
    vis.sort()
    return vis

ans = []
L = list(range(1,N0+1))

while L :
    VIS = bfs(graph,L[0])
    ans.append(VIS)
    for item in VIS :
        L.remove(item)
    
print(len(ans))

djm03178 3년 전 0

리스트에서 임의의 값을 remove하는 것은 그 원소를 찾고, 제거한 후 뒤에 있는 원소들을 전부 한 칸씩 당겨와야 하기 때문에 O(길이) 시간이 걸립니다.

choah76 3년 전 0

그럼 remove없이 i = 1 부터 i = N까지 bfs를 돌리는게 더 시간이 적게걸릴까요?

아니면 remove를 대체할 함수를 가르쳐주시면 감사하겠습니다. 아직 시간복잡도O(N)같은걸 배우지못한 학생이라 잘 모르겠습니다

djm03178 3년 전 0

지금의 vis나 VIS와 같은 구조 대신에, v[i]가 i번 정점을 방문했는가 여부를 나타내게 하는 리스트를 만들면 굳이 지우지 않아도 방문된 정점인지를 확인할 수 있습니다.

choah76 3년 전 0

그렇게 해보겠습니다

조언감사합니다!

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

문제

문제

출처

ICPC

[python 3] 11724 시간초과 해결법

choah76 3년 전 0

djm03178 3년 전 0

choah76 3년 전 0

djm03178 3년 전 0

choah76 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말