글 읽기 - 메모리 초과 발생 이유를 모르겠습니다.

lbg030 1년 전 0

제 생각에는 정석으로 bfs를 풀었다고 생각하는데

메모리 초과가 왜 발생하는지 잘 모르겠습니다.

이 문제 때문에 1시간 째 코드만 조금씩 바꿔가면서 시도 중인데 잘 모르겠네요 ..ㅜㅜ

from collections import deque

length,width,trash = map(int, input().split())

graph = [[0] * (width+1) for _ in range(length+1)]
check = [[False] * (width+1) for _ in range(length+1)]

for _ in range(trash):
    x, y = map(int, input().split())
    graph[x][y] = 1

#쓰래기 개수
result = 0
dx = [0,0,1,-1]
dy = [1,-1,0,0]

def bfs(x,y):
    cnt = 0
    queue = deque([(x,y)])
    while queue:
        
        x, y = queue.popleft()
        check[x][y] = True
        cnt += 1
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if 0 <= nx < length+1 and 0<= ny < width +1 :
                if graph[nx][ny] == 1 and check[nx][ny] == False:
                    queue.append((nx,ny))
    
    return cnt  

for i in range(1, length+1):
    for j in range(1, width+1):
        if graph[i][j] == 1 and check[i][j] == False:
            result = max(result, bfs(i,j))
            
print(result)

thproject 1년 전 0

앞에 글에 해결책이 잇는거같네요

import sys
sys.setrecursionlimit(100000)

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

문제

문제

출처

ICPC

메모리 초과 발생 이유를 모르겠습니다.

lbg030 1년 전 0

thproject 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말