글 읽기 - (파이썬 메모리초과) 메모리를 많이 사용한 곳이 어디인지 알려주세요!(주석o)

toctoce 1년 전 0

bfs함수를 두 번 사용해서 메모리가 너무 많이 사용 된 걸까요?

아니면 bfs함수를 돌릴 때 마다 visited 리스트를 생성해서 그런 건가요?

(14프로에서 메모리초과 나옵니다.)

from collections import deque
import sys

# 섬의 번호를 2,3,4,...로 정하는 함수(bfs)
def island_naming(lst):
    naming_q=deque([])
    island_number=1
    for i in range(N):
        for j in range(N):
            if lst[i][j]==1:
                island_number+=1
                naming_q.append((i,j))
                lst[i][j]=island_number
                while naming_q:
                    x,y=naming_q.popleft()
                    for dx,dy in [(0,1),(0,-1),(1,0),(-1,0)]:
                        nx,ny=x+dx,y+dy
                        if 0<=nx<N and 0<=ny<N:
                            if lst[nx][ny]==1:
                                lst[nx][ny]=island_number
                                naming_q.append((nx,ny))
    # 마지막 섬의 번호를 리턴
    return island_number
# 출발 섬이 num일 때, 다른 섬까지의 최소거리를 구하는 bfs
def bfs(num):
    q=deque()
    visited=[[False]*N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if island[i][j]==num:
                q.append((i,j,0))
                visited[i][j]=True
    while q:
        x,y,distance=q.popleft()
        for dx,dy in [(0,1),(0,-1),(1,0),(-1,0)]:
            nx,ny=x+dx,y+dy
            if 0<=nx<N and 0<=ny<N:
                if island[nx][ny]!=0 and island[nx][ny]!=num:
                    # 리턴값과 ans와의 최솟값을 ans에 저장
                    return distance
                if not visited[nx][ny]:
                    visited[i][j]=True
                    q.append((nx,ny,distance+1))

N=int(sys.stdin.readline())
island=[]
for _ in range(N):
    island.append(list(map(int,sys.stdin.readline().strip().split())))
ans=300
# 2부터 섬 중 가장 큰 번호까지 bfs함수를 돌림.
for i in range(2,island_naming(island)):
    # 리턴값과 ans와의 최솟값을 ans에 저장
    ans=min(bfs(i),ans)
print(ans)

dldyddlwl 1년 전 1

    while q:
        x,y,distance=q.popleft()
        for dx,dy in [(0,1),(0,-1),(1,0),(-1,0)]:
            nx,ny=x+dx,y+dy
            if 0<=nx<N and 0<=ny<N:
                if island[nx][ny]!=0 and island[nx][ny]!=num:

                    return distance
                if not visited[nx][ny]:
                    visited[i][j]=True        # 뭔가 이상하지 않습니까?
                    q.append((nx,ny,distance+1))

toctoce 1년 전 0

@dldyddlwl

헉 단순실수였네요!! 감사합니다~~! 정답 나왔습니다.

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

문제

문제

출처

ICPC

(파이썬 메모리초과) 메모리를 많이 사용한 곳이 어디인지 알려주세요!(주석o)

toctoce 1년 전 0

dldyddlwl 1년 전 1

toctoce 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말