글 읽기 - [python] 시간초과가 왜 날까요?

doublejy715 3년 전 0

저의 짧은 지식으로는 잘 이해가 가지 않습니다. 고수분들의 도움이 필요합니다 ㅜㅜ

23번째 줄에서 [next_y,next_x] not in need_visit 구문을 통해 이미 need_visit에 들어있는 경우 중복 순회를 피하기 위해서 조건을 걸어놨습니다.

나름 시간 단축을 위해서 걸어놓은 조건인데 오히려 시간초과가 발생했습니다.

두번째 정답 코드중 63번째 줄에 보시면 [next_y,next_x] not in need_visit를 없애고 그냥 돌렸는데 정답이 되었네요...

제 머릿속에는 오히려 두번째 코드가 더 길게 걸릴 것 같은데 왜 합격할 수 있게 되는것인지 고수분들의 고견 부탁드리겠습니다. ㅜㅜ

""" 첫 코드 """
import sys
from collections import deque

input = sys.stdin.readline
dy,dx = (1,-1,-2,-2,-1,1,2,2),(2,2,1,-1,-2,-2,-1,1)

""" Function """
def DFS():
    check = [[0] * I for __ in range(I)]
    need_visit = deque([[start_y,start_x]])
    check[start_y][start_x] = 1
    
    while need_visit:
        now_y, now_x = need_visit.popleft()
        # 기저조건
        if now_y == end_y and now_x == end_x:
            return check[end_y][end_x] - 1

        for i in range(8):
            next_y, next_x = now_y + dy[i], now_x + dx[i]
            if 0 <= next_y < I and 0 <= next_x < I:
                if check[next_y][next_x] == 0 and [next_y,next_x] not in need_visit:
                    check[next_y][next_x] = check[now_y][now_x] + 1
                    need_visit.append([next_y,next_x])

for _ in range(int(input())):
    """ Input """
    I = int(input())
    start_y,start_x = map(int,input().split())
    end_y, end_x = map(int,input().split())

    """ Solve """
    if start_y == end_y and start_x == end_x:
        print(0)
        continue

    print(DFS())
    
    
""" 정답 코드 """
import sys
from collections import deque

input = sys.stdin.readline
dy,dx = (1,-1,-2,-2,-1,1,2,2),(2,2,1,-1,-2,-2,-1,1)

""" Function """
def DFS():
    check = [[0] * I for __ in range(I)]
    need_visit = deque([[start_y,start_x]])
    check[start_y][start_x] = 1

    while need_visit:
        now_y, now_x = need_visit.popleft()
        # 기저조건
        if now_y == end_y and now_x == end_x:
            return check[end_y][end_x] - 1

        for i in range(8):
            next_y, next_x = now_y + dy[i], now_x + dx[i]
            if 0 <= next_y < I and 0 <= next_x < I:
                if check[next_y][next_x] == 0:
                    check[next_y][next_x] = check[now_y][now_x] + 1
                    need_visit.append([next_y,next_x])

for _ in range(int(input())):
    """ Input """
    I = int(input())
    start_y,start_x = map(int,input().split())
    end_y, end_x = map(int,input().split())

    """ Solve """
    if start_y == end_y and start_x == end_x:
        print(0)
        continue

    print(DFS())

kokodak 3년 전 1

고수는 아니지만 감히 글 써보면, not in 연산자가 가지는 시간복잡도가 O(len(need_visit))일텐데, 이 시간복잡도에 의해 발생하는 연산량이 너무 커서 그런 것 같습니다.

저 코드에 최대치로 들어올 수 있는 입력 값을 대충 넣어봤는데, [next_y,next_x] not in need_visit 조건에만 80000번 이상이 걸리고 need_visit의 최대크기가 2-30000까지 올라가는데, need_visit의 크기가 항상 2-30000이 유지되는게 아니기 때문에 평균적으로 5000으로 잡아도 80000 * 5000 = 4억이니까 1초 시간제한에는 너무 큰 연산량인 것 같습니다.

게다가, 이 문제는 테스트 케이스를 따로 받아서 여러 번 계산해야하기 때문에 O(len(need_visit)) 시간복잡도를 무시할 수가 없을 것 같습니다.

doublejy715 3년 전 0

감사합니다. 덕분에 궁금증이 풀렸습니다.

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

문제

문제

출처

ICPC

[python] 시간초과가 왜 날까요?

doublejy715 3년 전 0

kokodak 3년 전 1

doublejy715 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말