[백준 파이썬 2638번 치즈] 구현 최적화

최초 코드

from collections import deque

def findCheese():
    ls = []
    for row in range(N):
        for col in range(M):
            if graph[row][col] == 1:
                ls.append((row, col))
            if graph[row][col] == -1:
                graph[row][col] = 0
    return ls

def bfs():
    q = deque()
    q.append((0, 0))

    while q:
        r, c = q.popleft()

        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]

            if nr < 0 or nc < 0 or nr >= N or nc >= M:
                continue
            if graph[nr][nc] == 0:
                graph[nr][nc] = -1
                q.append((nr, nc))

def remove(ls):
    remove_ls = []
    for r, c in ls:
        cnt = 0
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]

            if graph[nr][nc] == -1:
                cnt += 1

        if cnt < 2:
            continue
        else:
            remove_ls.append((r, c))

    for r, c in remove_ls:
        graph[r][c] = 0

dr = [1, 0, -1, 0]
dc = [0, 1, 0, -1]

N, M = map(int, input().split())
graph = []
for _ in range(N):
    graph.append(list(map(int, input().split())))

time = 0
cheese_ls = findCheese()

while cheese_ls:
    time += 1
    bfs()
    remove(cheese_ls)
    cheese_ls = findCheese()

print(time)

뭔가 복잡한 최초 코드;;

시간도 오래 걸렸다

 

최적화

import sys; input = sys.stdin.readline
N, M = map(int, input().split())

graph = [[-1] * (M + 2)]
for _ in range(N):
    graph.append([-1] + list(map(int, input().split())) + [-1])
graph.append(graph[0])

direc = ((-1, 0), (0, -1), (0, 1), (1, 0))

time = -1
queue, next_queue = [(1, 1)], []
while queue:
    time += 1
    while queue:
        r, c = queue.pop()
        for dr, dc in direc:
            nr, nc = r + dr, c + dc
            if graph[nr][nc] > 0: # 치즈
                graph[nr][nc] += 1
                if graph[nr][nc] > 2:
                    graph[nr][nc] = -1
                    next_queue.append((nr, nc)) # 치즈 to 외부 공기
            elif graph[nr][nc] == 0: # 공기
                graph[nr][nc] = -1 # 외부 공기
                queue.append((nr, nc)) # 외부 공기 파악
    queue, next_queue = next_queue, queue

print(time)

1초 경과 후 치즈를 지우고 다시 치즈를 찾지말고

치즈에 닿은 공기 숫자를 적어두고 새로운 공기가 생기면 그 새로 생긴 공기만 다시 탐색을 돌린다

-> 치즈가 없어지면 그 자리는 새로운 공기이기 때문에 그거만 고려