글 읽기 - 반례를 찾고 싶습니다

qpple6 2년 전 0

잘 돌아가다가 82%에서 잠시 멈춘뒤에 시간초과 오류가 발생합니다.

게시판에 있는 질문들도 모두 보고 경계값도 해본 만큼 해본 것 같은데

82%에서 무한루프에 빠지는건지,, 또 그 이유가 뭔지 잘 모르겠습니다ㅠㅠ

혹시 코드에 대한 반례가 있을까요 궁금합니다...!

from collections import deque

a, b = map(int, input().split())
arr = []
dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, 1, 1, 1, 0, -1, -1, -1]
for i in range(a):
    arr.append(list(map(int, input().split())))
    
result = [0]
def bfs(x, y):
    
    q = deque()
    q.append((x, y))
    depth = [[-1] * b for _ in range(a)]
    depth[x][y] = 0
    
    while q:
        x, y = q.popleft()
        
        for k in range(8):
            
            nx = x + dx[k]
            ny = y + dy[k]
            
            if nx < 0 or ny < 0 or nx >= a or ny >= b:
                continue
                
            if arr[nx][ny] == 0 and depth[nx][ny] == -1:
                q.append((nx, ny))
                depth[nx][ny] = depth[x][y] + 1
                
            if arr[nx][ny] == 1 and depth[nx][ny] == -1:   
                #1이 존재하면
                return depth[x][y] + 1
                #최댓로 잴 수 있는 안전거리 리턴
            
            
    
    
for i in range(a):
    for j in range(b):
        if arr[i][j] == 0:
            result.append(bfs(i, j))
            
if None in result:
    print(0)
else:
    #각 점에서 안전거리 중 최대값 출력
    print(max(result))
            

fromecha 2년 전 1

근본적인 문제 해결은 아니지만 pypy3로 돌리시면 통과됩니다

저도 82퍼에서 시간 초과나서 sys도 사용해보고 시간 줄여보려고 이것저것 해봤지만 python3에서는 시간초과가 뜨네요

qpple6 2년 전 0

아 맞네요.. pypy3으로 하니까 통과되긴 했습니다! 파이썬에서는 시간을 좀 더 단축시켜야 하나 보네요...ㅠ

감사합니다!

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

문제

문제

출처

ICPC

반례를 찾고 싶습니다

qpple6 2년 전 0

fromecha 2년 전 1

qpple6 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말