boj.kr/2638 치즈 (gold3) 파이썬 풀이

dfs 방식으로 풀이 시도한 결과 테스트 케이스는 통과했지만 제출시 시간 초과 또는 메모리 초과가 발생했다.

dfs 풀이(시간초과)

N, M = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(N)]
visited = [[False]*M for _ in range(N)]

dy = (1, -1, 0, 0)
dx = (0, 0, 1, -1)

from collections import deque

def bfs(y, x):
    dq = deque()
    dq.append((y, x))

    while dq:
        (y, x) = dq.popleft()
        graph[y][x] = -2
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if 0 <= ny < N and 0 <= nx < M and graph[ny][nx] == 0 and not visited[ny][nx]:
                visited[ny][nx] = True
                dq.append((ny, nx))

visited[0][0] = True
bfs(0, 0)

def get_cheese_set():
    global cheese_set
    for y in range(N):
        for x in range(M):
            if graph[y][x] == 1:
                cheese_set.add((y, x))
    return cheese_set

def one_hour_later():
    for (y, x) in list(cheese_set):
        cnt = 0
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if 0 <= ny < N and 0 <= nx < M and graph[ny][nx] == -2:
               cnt+=1
        if cnt >= 2:
            graph[y][x] = -2
            cheese_set.remove((y, x))

hour_cnt = 1
cheese_set = set()
cheese_set = get_cheese_set()

while len(cheese_set) > 0:
    one_hour_later()
    hour_cnt += 1

print(hour_cnt)

 

정답 풀이

1. 남은 치즈가 없을 떄까지 아래를 반복

1.1. 치즈여부 graph에 대해 bfs를 아래와 같이 실행한다.

1.1.1.  체크 배열 chk를 graph 크기만큼 0으로 초기화

1.1.2. deque에 (0, 0)을 추가

1.1.3. chk[0][0]을 1으로 갱신

1.1.4 dq가 빌 때까지 아래를 반복

1.1.4.1. (cy, cx) 으로 dq.popleft()한 값을 저장

1.1.4.2. (cy, cx)의 상하좌우 좌표에 대하여 각각 아래를 검사하고 수행

1.1.4.2.1. 그래프상의 좌표이고 그래프의 해당좌표값이 0이면서 체크배열의 해당좌표값이 0이거나, 그래프의 해당좌표값이 1이면서 체크배열의 해당좌표값이 2보다 크지 않으면, 체크배열의 해당좌표값을 1 증감, 그래프의 해당좌표값이 0이면 deque에 해당 좌표를 추가, 그래프의 해당좌표값이 1이면서 체크배열의 해당좌표값이 2이면 그래프의 해당좌표값을 0으로 갱신

1.2. bfs를 종료 후 hours 카운트를 1 증감

2. 남은 치즈가 없으므로 hours 카운트를 출력

 

N, M = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(N)]
dy = [1, -1, 0, 0]
dx = [0, 0, 1, -1]
from collections import deque

def bfs():
    chk = [[0 for _ in range(M)] for _ in range(N)]
    dq = deque()
    dq.append((0, 0))
    chk[0][0] = 1
    while dq:
        (cy, cx) = dq.popleft()
        for i in range(4):
            ny = cy + dy[i]
            nx = cx + dx[i]
            if 0<=ny<N and 0<=nx<M and ((graph[ny][nx] == 0 and chk[ny][nx] == 0) 
                                     	or (graph[ny][nx] == 1 and not chk[ny][nx] > 2)):
                chk[ny][nx] += 1
                if graph[ny][nx] == 0:
                    dq.append((ny, nx))
                if graph[ny][nx] == 1 and chk[ny][nx] == 2:
                    graph[ny][nx] = 0

def is_no_cheese_left():
    tot = 0
    for _ in graph:
        tot += sum(_)
    return tot == 0

hours = 0
while True:
    if is_no_cheese_left():
        break
    bfs()
    hours += 1

print(hours)

 

bfs 방식으로 풀이해야 모든 테스트 케이스에 대해 시간 초과 또는 메모리 초과가 발생하지 않는다.