글 읽기 - 파이썬 bfs 시간초과 오류

zxaq15 4년 전 0

채점중 2%에서 더 이상 안올라가고 한 2~30초있다가 시간초과오류가 뜨는데

제 코드가 느려서 뜨는건지 사이트 오류인지를 모르겠습니다.

def bfs(start_x, start_y):
    visited[start_x][start_y] = True
    queue = [start_x]
    is_cycle = False
    while queue:
        search_x = queue.pop(0)
        for i in range(n+1):
            if not visited[search_x][i] and matrix[search_x][i]:
                visited[search_x][i] = True
                queue.append(i)
                is_cycle = True
    return is_cycle


n, m = map(int, input().split())
visited = [[False]*(n+1) for _ in range(n+1)]
matrix = [[0]*(n+1) for _ in range(n+1)]
for i in range(m):
    u, v = map(int, input().split())
    matrix[u][v] = 1
    matrix[v][u] = 1


cnt = 0
for i in range(n+1):
    for j in range(n+1):
        if not visited[i][j]:
            if bfs(i, j):
                cnt += 1

print(cnt)

dkssudckdah 4년 전 0

visited와 matrix에 불필요하게 차지하는 부분이 많이 있는 것 같습니다.

문제에 주어진 예제에서 matrix에 [1,3], [1,4], [1,6] 부분은 필요가 없습니다.

zxaq15 4년 전 0

무슨뜻인가요? 이해를 못했습니다.

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

문제

문제

출처

ICPC

파이썬 bfs 시간초과 오류

zxaq15 4년 전 0

dkssudckdah 4년 전 0

zxaq15 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말