DFS : 음료수 얼려먹기

N,M = map(int, input().split(' '))
arr = []
for _ in range(N):
    arr.append(list(map(int, list(input()))))
def dfs(row, col):
    if row >= 0 and row <N and col>=0 and col<M:
        if arr[row][col] == 0:
            arr[row][col] = 1
            dfs(row+1, col)
            dfs(row-1, col)
            dfs(row, col+1)
            dfs(row, col-1)
            return True
        return False
answer = 0
for n in range(N):
    for m in range(M):
        if arr[n][m] == 0:
            if dfs(n, m) == True:
                answer += 1
dfs(0,0)
print(answer)

BFS: 미로 탈출

from collections import deque
N,M = map(int, input().split())
arr = [list(map(int, input())) for _ in range(N)]

dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
roads = []
def bfs(row, col):
    queue = deque()
    queue.append((row, col))
    while queue:
        # dfs와의 차이: 반복을 재귀가 아닌 while문으로 
        row,col = queue.popleft()
        for i in range(4):
            d_row = row + dy[i]
            d_col = col + dx[i]
            if d_row >= 0 and d_row < N and d_col >=0 and d_col < M:
                if arr[d_row][d_col] == 1:
                    arr[d_row][d_col] = arr[row][col]+1
                    queue.append((d_row, d_col))            
                    if d_row == N-1 and d_col == M-1:
                        roads.append(arr[d_row][d_col])

bfs(0,0)
print(roads)