[백준] 4179 불! (파이썬/python) (with 메모리 초과)

🎈문제

https://www.acmicpc.net/problem/4179

 

🎁어떤 알고리즘?

1. 불은 각 지점에서 네 방향으로 확산된다 -> bfs 임을 알 수 있다.

2. 지훈이와 불은 매 분마다 한칸씩 수평 또는 수직으로 이동한다. -> bfs 임을 알 수 있다.

3. 불이 타기전에 탈출하려면 불이 언제 어디까지 퍼지는지 알 수 있어야 한다. 불이 언제 어디까지 퍼지는지  graph에 표시한 뒤, 지훈이의 이동시간을 덮어씌워주면 됨!

4. 불이 번지지 않은 곳은 여전히 해당 좌표의 값이 '.' 임을 꼭 기억하고 코드 작성하기!

4. 메모리 초과 글은 밑에 있음

 

💻코드

from collections import deque

def f_bfs():
    while f_deq:
        x,y = f_deq.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # graph 벗어난 좌표는 무시
            if nx < 0 or nx > (r-1) or ny < 0 or ny > (c-1): 
                continue
            '''
            'J'에 해당하는 좌표는 0으로 미리 바꿔뒀기 때문에
            graph[nx][ny] == '.'일 때만 불이 이동할 수 있도록 함.
            '''
            if graph[nx][ny] == '.':
                graph[nx][ny] = graph[x][y] + 1
                f_deq.append([nx,ny])

def j_bfs():
    while j_deq:
        x,y = j_deq.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # graph를 벗어나면 탈출했음을 의미한다.
            if nx < 0 or nx > (r-1) or ny < 0 or ny > (c-1):
                time = graph[x][y] + 1
                return print(time)  # 탈출!
             #불이 번지지 않았으면 해당 좌표값이 '.'인 경우도 있음을 고려
            if graph[nx][ny] == '.':
                graph[nx][ny] = graph[x][y] + 1
                j_deq.append([nx,ny])
            # 해당 좌표값이 '#'이면 밑의 if문이 오류가 나서 걸러주기 위해 추가
            elif graph[nx][ny] != '#':
                if graph[nx][ny] > (graph[x][y] + 1): # 불의 값이 지훈이보다 크면
                    graph[nx][ny] = graph[x][y] + 1
                    j_deq.append([nx,ny])
    time = 'IMPOSSIBLE' # 지훈이가 탈출하지 못하면 이 문장에 도달   
    return print(time)

# r: 행(x), c: 열(y)
r,c = map(int,input().split())

# graph
graph = []
for i in range(r):
    graph.append(list(input()))

#deque
j_deq = deque()
f_deq = deque()
dx = [0,0,-1,1]
dy = [-1,1,0,0]

# 지훈, 불 처음 위치 큐에 넣기
for i in range(r):
    for j in range(c):
        if graph[i][j] == 'F':
            f_deq.append([i,j])
            graph[i][j] = 0 # 0부터 시작해서 해당 위치 시간 파악
        if graph[i][j] == 'J':
            j_deq.append([i,j])
            graph[i][j]= 0  # 0부터 시작해서 해당 위치 시간 파악

f_bfs() # 불 먼저 bfs돌려서 언제 어디까지 퍼지는지 graph에 표기
j_bfs()

코드 실행 결과 순서

 

❗ 메모리 초과

사실 이 문제를 보게되면 가장 먼저 들었던 생각이 fire리스트와 jihoon리스트를 만들어서 이동한 흔적을 여기에 남길까? 였다. 그러나 graph에 fire리스트, jihoon리스트까지 관리하게 되자, 바로 메모리 초과 오류가 떴고,, ㅜㅜ 그래서 코드가 조금 지저분하지만 graph내에 불과 지훈이의 시간을 모두 표기하는 코드로 다 갈아엎었다.

 

 

💻메모리 오류 코드

from collections import deque

def fire_bfs():
    while f_deq:
        x,y = f_deq.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # graph 벗어난 좌표는 무시
            if nx < 0 or nx > (r-1) or ny < 0 or ny > (c-1):
                continue
            if graph[nx][ny] == '#' or fire[nx][ny] > 0:
                continue
            if graph[nx][ny] == '.' or graph[nx][ny] == 'J':
                fire[nx][ny] = fire[x][y] + 1
                f_deq.append([nx,ny])

def jihoon_bfs():
    # print('jihoon')
    while j_deq:
        x,y = j_deq.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx > (r-1) or ny < 0 or ny > (c-1): # 탈출
                time = jihoon[x][y] + 1
                return print(time)
            if graph[nx][ny] == '#' or fire[nx][ny] <= (jihoon[x][y]+1):
                continue
            if graph[nx][ny] == '.' or graph[nx][ny] == 'F':
                jihoon[nx][ny] = jihoon[x][y] + 1
                j_deq.append([nx,ny])
    time = 'IMPOSSIBLE' # 탈출 못 하면 실행됨  
    return print(time)

# r: 행(x), c: 열(y)
r,c = map(int,input().split())

# graph
graph = []
for i in range(r):
    graph.append(list(input()))
# 불, 지훈 위치 표기할 리스트
jihoon = [[0 for j in range(c)] for i in range(r)]
fire = [[0 for j in range(c)] for i in range(r)]
#deque
j_deq = deque()
f_deq = deque()
dx = [0,0,-1,1]
dy = [-1,1,0,0]

# 지훈, 불 처음 위치 큐에 넣기
for i in range(r):
    for j in range(c):
        if graph[i][j] == 'F':
            f_deq.append([i,j])
        if graph[i][j] == 'J':
            j_deq.append([i,j])

fire_bfs()
jihoon_bfs()