[이코테] DFS/BFS 실전문제 3 음료수 얼려 먹기

전형적인 DFS 문제였다

여기로 갔다가 어떻게 돌아오지? 라는 생각이 들면

무조건 재귀를 떠올릴 것

너무 시간을 많이 까먹는게 아니라면 시간복잡도에 걸릴 일도 없고

효율적으로 탐색할 수 있다

import sys
# sys.stdin.readline()
from collections import deque
sys.setrecursionlimit(100000000)
import heapq
INF = int(1e9)
def dfs(graph,row,col,N,M):
    if row < 0 or row >= N or col < 0 or col >= M:
        return False
    if graph[row][col] == 0:
     graph[row][col] = 1
     dfs(graph,row+1,col,N,M)
     dfs(graph,row,col+1,N,M)
     dfs(graph,row-1,col,N,M)
     dfs(graph,row,col-1,N,M)
    return False

    
N,M = map(int,sys.stdin.readline().split())
graph =[]

for i in range(N):
 graph.append(list(map(int,sys.stdin.readline().rstrip())))
count = 0
for i in range(N):
    for j in range(M):
        if graph[i][j] == 0:
            dfs(graph,i,j,N,M)
            count +=1

print(count)

피드백 할거는

N,M을 위에 입력받고

함수를 아래부분에 썼으면 함수 인자가 복잡해지지 않았을 것

 

하여튼 요약

DFS : 스택 이용, Deep하게 깊이 우선 탐색 / 재귀 방식 이용

BFS: 큐 이용 (파이썬은 queue = deque()가 일반적) , 너비 우선 탐색, 재귀 방식 아니라서 마음에 든다.