글 읽기 - 시간초과관련

yundabin0608 2년 전 0

다음처럼 코드를 작성하면 60프로에 시간초과가 뜹니다

Pypy3에선 정답이 뜨는데 어떤 부분때문에 그러는지 모르겠어서 질문 남깁니다.

import sys
from collections import deque
input=sys.stdin.readline

n,m = map(int, input().split())
graph = []   # 보물섬 지도표시
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

def bfs(x,y,cnt):
    visited = [[0]*m for _ in range(n)]
    count = 0
    queue = deque()
    queue.append((x,y,cnt))
    visited[y][x]=1
    while queue:
        tx, ty, tcnt = queue.popleft()
        if count < tcnt: count=tcnt  # count를 최대값으로 유지
        for i in range(4):
            nx = tx+dx[i]
            ny = ty+dy[i]
            if 0<=nx<m and 0<=ny<n and graph[ny][nx]=='L' and visited[ny][nx]==0:
                # nx, ny 가 범위내에 존재하고 육지이며 방문한 적 없을경우
                # 방문표시 후 현좌표 cnt에 다음좌표로 갈땐 cnt+1로 1 더함
                visited[ny][nx]=1
                queue.append((nx,ny,tcnt+1))
    return count  

# n 세로 m 가로
for _ in range(n):
    # 리스트 생성시 '\n' 제거를 위해 rstrip() 함수 이용
    graph.append(list(input().rstrip())) 
    
result=0
for y in range(n):
    for x in range(m):
        if graph[y][x] == 'L':
            result=max(result, bfs(x,y,0)) 
            # 각각의 자리에서 실행했던 결과들 중 최댓값으로 매번 갱신
print(result)

qvixnh22 2년 전 0

python3와 pypy3는 구현체가 다릅니다. 실제 메모리 사용량과 수행 시간에서 차이가 있을 수 있습니다. 그렇지 않은 상황도 있지만 많은 상황에서 pypy3가 메모리를 많이 소모하여 빠른 계산을 하게 됩니다.

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

문제

문제

출처

ICPC

시간초과관련

yundabin0608 2년 전 0

qvixnh22 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말