글 읽기 - 3197 백조의 호수 메모리 초과

khsh5592 3년 전 0

전체 코드는

1. melt() 빙산 녹이기

2. BFS() 백조 경로 탐색하기

순으로 진행됩니다. 메모리 초과를 해결할 다른 방법이 있을까요.

import sys
from collections import deque

dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]

def BFS():
    temp = deque()
    while swan:
        x, y = swan.popleft()

        if x == end[0] and y == end[1]:
            return True

        if not lake[x][y] == 'L':
            lake[x][y] = 1

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < R and 0 <= ny < C:
                if lake[nx][ny] =='.':
                    lake[nx][ny] = 1
                    swan.append((nx, ny))
                else:
                    temp.append((nx, ny))
    return temp

def melt():
    temp = deque()
    while water:
        x, y = water.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < R and 0 <= ny < C:
                if lake[nx][ny] == 'X':
                    lake[nx][ny] = '.'
                    temp.append((nx, ny))
    return temp


R, C = map(int, sys.stdin.readline().split())

lake = []

for _ in range(R):
    lake.append(list(str(sys.stdin.readline().strip())))

water = deque()
swan = deque()
for i in range(R):
    for j in range(C):
        if lake[i][j] == 'L':
            swan.append((i, j))
            water.append((i, j))
        elif lake[i][j] == '.':
            water.append((i, j))
time = 0
end = swan.pop()

while True:
    water = melt()
    swan = BFS()
    if swan == True:
        print(time)
        break
    time += 1

khsh5592 3년 전 0

해결했습니다. 함수 호출을 최소화 하니까 해결이 됐습니다.

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

문제

문제

출처

ICPC

3197 백조의 호수 메모리 초과

khsh5592 3년 전 0

khsh5592 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말