글 읽기 - python 시간초과 질문입니다.

wwlee94 4년 전 1

bfs를 이용하여 풀었고 시간초과 난 코드입니다.

0 100000 입력하면 너무 오래걸리네요

다음 방문할 노드(queue) 와 방문한 노드를 저장한 리스트(visited)를 출력해보면 중복 방문하는 것 같진 않습니다.

31번 라인의 조건의 문제같은데 조언부탁드립니다.

import sys
from collections import deque

input_s = lambda: sys.stdin.readline().strip()

N, K = map(int, input_s().split())

time = 0
visited = deque()
queue = deque()


def search_bfs(start):
    global time

    queue.append(start)
    visited.append(start)

    while queue:

        size = len(queue)
        for _ in range(size):
            next_start = queue.popleft()

            next_queue = deque()
            next_queue.append(next_start - 1)  # left
            next_queue.append(next_start + 1)  # right
            next_queue.append(2 * next_start)  # jump

            for v in next_queue:
                if v not in visited and v <= 2*K and v >= N:
                    queue.append(v)
                    visited.append(v)
        # print(queue)
        # print(visited)
        time += 1
        if K in queue:
            return time


def solution():
    global time
    if N >= K:
        time = N - K
    else:
        search_bfs(N)

    return time


result = solution()
print(result)

wwlee94 4년 전 1

중복 방문 검사를 deque에 넣어 진행해서

너무 오래 걸린것 같습니다.

visited = [0]* 100001 를 만들어서 중복 검사 진행하니 해결 되었습니다

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

문제

문제

출처

ICPC

python 시간초과 질문입니다.

wwlee94 4년 전 1

wwlee94 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말