글 읽기 - python3에서의 시간초과 질문입니다.

kangmj921 1년 전 0

바이러스가 위치할 수 있는 곳을 조합으로 구한 뒤, 조합으로 올 수 있는 위치들을 반복문으로 돌리면서

바이러스가 퍼지는 과정을 bfs를 이용하여 구현하였는데요, 기묘하게 bfs 구현한 부분을

반복문 안에서 함수로 따로 빼면 시간초과가 걸리지 않고

그냥 반복문 안에서 그대로 구현해 버리면 시간초과가 납니다.

두 코드의 시간복잡도에서 어떤 차이가 있는 건가요....

# python3에서 시간초과에 걸리는 코드
# for v_m in virus_location:
#     queue = deque()
#     visit = [[-1] * N for _ in range(N)]
#     cnt = 0
#     result = 0
#     for y, x in v_m:
#         queue.append((y, x))
#         visit[y][x] = 0
#     while queue:
#         y, x = queue.popleft()
#         for i in range(4):
#             ny = y + dy[i]
#             nx = x + dx[i]
#             if ny < 0 or nx < 0 or ny >= N or nx >= N or lab[ny][nx] == 1 or visit[ny][nx] != -1:
#                 continue
#             visit[ny][nx] = visit[y][x] + 1
#             if not lab[ny][nx]:
#                 result += 1
#                 cnt = max(cnt, visit[ny][nx])
#             queue.append((ny, nx))
#     if count == result:
#         answer = min(answer, cnt)
if __name__ == '__main__':
    visit_dict = {}
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    N, M = map(int, sys.stdin.readline().split())
    # N(4 ≤ N ≤ 50), M(1 ≤ M ≤ 10)
    lab = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
    # 0은 빈 칸, 1은 벽, 2는 바이러스를 놓을 수 있는 위치
    temp, virus_location = [], []
    answer = []
    result = 0
    for i in range(N):
        for j in range(N):
            if not lab[i][j]:
                result += 1
            if lab[i][j] == 2:
                temp.append((i, j))  # M보다 크거나 같고 10보다 작거나 같음.
    # 모든 바이러스를 놓을 수 있는 위치 중 M개의 조합을 찾아서 계산하면
    # 10CM 개의 경우를 얻을 수 있다. 이 경우 최대 10C5 = 252, O(V + E) = O(2500) * O(2500)
    combination_by_m(0, [])
    # python3에서 시간초과에 걸리지 않는 코드
    for v_m in virus_location:  # 최대 252번.
        bfs(v_m, result)  # bfs를 함수로 빼면 시간초과가 안걸린다?
    print(min(answer) if answer else -1)

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

문제

문제

출처

ICPC

python3에서의 시간초과 질문입니다.

kangmj921 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말