글 읽기 - 메모리 초과 관련하여 질문 드립니다.

nakalic 2년 전 0

로직을 잘못 짠 것인가요? 아니면 무한루프가 발생되는 것일까요 ?

불의 이동시간을 먼저 계산하고 그 뒤에 maze 리스트에서 위치가 fire 보다 적을 때만 BFS 돌리는 식으로 했는데

메모리 초과가 발생하네요 ㅜㅜ

import sys
from collections import deque

input = sys.stdin.readline

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

R, C = map(int, input().split())

temp = [list(input().strip()) for _ in range(R)]
maze = [[0] * C for _ in range(R)]
fire = [[0] * C for _ in range(R)]

fqueue = deque()
mqueue = deque()

for i in range(R):
    for j in range(C):
        if temp[i][j] == '#':
            maze[i][j] = -1
            fire[i][j] = -1
        elif temp[i][j] == 'J':
            maze[i][j] = 1
            mqueue.append((i, j))
        elif temp[i][j] == 'F':
            fire[i][j] = 1
            fqueue.append((i, j))
        elif temp[i][j] == '.':
            maze[i][j] = 0
            fire[i][j] = 0

ans = "IMPOSSIBLE"
while fqueue:
    x, y = fqueue.popleft()
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < R and 0 <= ny < C:
            if fire[nx][ny] == 0:
                fire[nx][ny] = fire[x][y] + 1
                fqueue.append((nx, ny))

while mqueue:
    x, y = mqueue.popleft()
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < R and 0 <= ny < C:
            if maze[x][y] + 1 < fire[nx][ny]:
                maze[nx][ny] = maze[x][y] + 1
                mqueue.append((nx, ny))
        else:
            ans = maze[x][y]

print(ans)

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

문제

문제

출처

ICPC

메모리 초과 관련하여 질문 드립니다.

nakalic 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말