글 읽기 - 리스트큐 시간 초과 set큐 성공

reo1947 2년 전 0

처음 큐를 리스트로 설정하고 탐색하면 시간초과가 나오는데

세트로 설정하고 탐색하니 정상적으로 작동하는데 그 이유를 잘 모르겠습니다

혹시 왜 그런건지 아시는 분 있으신가요?

# 1
def bfs(x,y):
    answer = 1
    temp = [[0,0,-1,1], [1,-1,0,0]]

    q = list([(x,y,graph[x][y])])

    while q:
        x1,y1,ans = q.pop()

        for i in range(4):
            tX = x1 + temp[0][i]
            tY = y1 + temp[1][i]

            if 0 <= tX < n and 0 <= tY < m and graph[tX][tY] not in ans:
                q.append((tX,tY, ans + graph[tX][tY]))
                answer = max(answer, len(ans) + 1)
    return answer

# 2
def bfs(x,y):
    answer = 1
    temp = [[0,0,-1,1], [1,-1,0,0]]

    q = set([(x,y,graph[x][y])])

    while q:
        x1,y1,ans = q.pop()

        for i in range(4):
            tX = x1 + temp[0][i]
            tY = y1 + temp[1][i]

            if 0 <= tX < n and 0 <= tY < m and graph[tX][tY] not in ans:
                q.add((tX,tY, ans + graph[tX][tY]))
                answer = max(answer, len(ans) + 1)
    return answer

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

문제

문제

출처

ICPC

리스트큐 시간 초과 set큐 성공

reo1947 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말