글 읽기 - python 시간 초과에 대해서

tipsyboy 1년 전 0

제 코드에서 제가 생각한 계산 값은 O((NM)^2) 인데, N, M의 범위가 50으로 충분히 가능하다고 판단했으나 시간 초과를 받았습니다.

물론, pypy로 통과는 했지만, python에서 통과 못할 이유가 없어 보이는데 ㅠ 혹시 제가 잘못 생각한 부분이 있을까요..?

import sys
from collections import deque

input = sys.stdin.readline
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]


def bfs(sx: int, sy: int) -> int:
    q = deque([(sx, sy)])
    visited = [[-1] * M for _ in range(N)]
    visited[sx][sy] = 0

    longest = 0
    while q:
        x, y = q.popleft()

        for i in range(4):
            nx, ny = x + directions[i][0], y + directions[i][1]

            if nx < 0 or nx >= N or ny < 0 or ny >= M:
                continue
            if graph[nx][ny] == "W" or visited[nx][ny] != -1:
                continue

            q.append((nx, ny))
            visited[nx][ny] = visited[x][y] + 1
            longest = max(longest, visited[nx][ny])

    return longest


N, M = map(int, input().split())
graph = [list(input().rstrip()) for _ in range(N)]

ans = 0
for i in range(N):
    for j in range(M):
        if graph[i][j] == "W":
            continue
        ans = max(ans, bfs(i, j))
print(ans)

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

문제

문제

출처

ICPC

python 시간 초과에 대해서

tipsyboy 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말