글 읽기 - 동일 코드로 pypy는 정답인데 python3로는 시간초과 입니다

dbsalvl123 3년 전 0

일단 아이디어는 기본적인 bfs를 이용하여 문제를 해결했습니다. for문을 통해 방문하지 않은 노드의 경우

해당 노드를 매개변수로 넘겨주어 bfs를 호출합니다. 매개변수로 받은 노드는 1로 방문을 해주고 bfs를 수행하며

방문할 노드의 전 노드가 1인 경우 2로 방문처리, 전 노드가 2인 경우 1로 방문처리를 해줍니다. 방문한 노드인 경우

전 노드와 1,1 로 혹은 2,2로 같으면0을 반환하는 식으로 해결합니다. 똑같은 코드를 pypy로 채점을 하면 정답처리를 받는데 python으로

돌리면 시간초과가 나더군요. 제가 생각할때는 잘 모르겠어서 고수님들의 도움을 받고싶네요

어떤 경우로 인해 시간 초과가 나고 이를 python3에서 정답처리를 받으려면 어떻게 최적화를 해야할까요??

from collections import deque

K = int(input()) # test case
for _ in range(K):
  V, E = map(int, input().split())
  graph = [[] for _ in range(V + 1)]
  visited = [0] * (V + 1)
  c = [0] * (V + 1)
  for i in range(E):
    start, end = map(int, input().split())
    graph[start].append(end)
    graph[end].append(start)

  def bfs(start):
    queue = deque()
    queue.append(start)
    visited[start] = 1
    while queue:
      v = queue.popleft()
      for i in graph[v]:
        if not visited[i]:
          if visited[v] == 1:
            visited[i] = 2
          elif visited[v] == 2:
            visited[i] = 1
          queue.append(i)
        elif visited[i] == visited[v]:
          return 0
    return 1
    
  check = False
  for i in range(V):
    if visited[i] == 0: # 아직 방문하지 않은 경우
      ans = bfs(i)
      if ans == 0: # 이분안되는 경우 check 를 True로 재정의
        check = True 
        break

  if check == True:
    print("NO")
  else:
    print("YES")
      

whdgurclzls 3년 전 0

파이썬이 많이 느리기 때문에 같은 코드인데 pypy로만 통과하는 문제가 생각보다 많습니다.

이 문제 같은 경우에는 줄로 된 입력이 많아서 입력을 sys.stdin.readline()으로 받으면 많이 빨라질것으로 예상됩니다.

#첫줄 or 두번째줄에 다음 코드 추가
from sys import*
input = stdin.readline

dbsalvl123 3년 전 0

감사합니다~~~~

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

문제

문제

출처

ICPC

동일 코드로 pypy는 정답인데 python3로는 시간초과 입니다

dbsalvl123 3년 전 0

whdgurclzls 3년 전 0

dbsalvl123 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말