11. DFS/BFS : 음료수 얼려 먹기

input: 

n m (n * m 얼음판)

00110

00011

11111

00000 (0은 비어있는 것)

 

rule:

0은 상하좌우로 붙어 있으며 1은 칸막이. 위의 예시는 총 3 개의 음료수가 얼려진다.

위처럼 입력 받았을 때 생성되는 음료수 얼음의 개수를 찾으시오.

 

dfs 알고리즘을 활용한다. 추후 bfs로도 풀 수 있는 지 확인 필요.

graph = []

n,m = map(int,input().split())

for i in range(n):
  graph.append(list(map(int,input())))



def dfs(x,y):
  
  if x <= -1 or x >=n or y <= -1 or y >= m:
    return False
  if graph[x][y] == 0:
    graph[x][y] = 1
    dfs(x-1,y)
    dfs(x,y-1)
    dfs(x+1,y)
    dfs(x,y+1)
    return True
  
  return False

count = 0
for i in range(n):
  for j in range(m):
    if dfs(i,j) :
      count += 1
print(count)

상하좌우로 탐색하는 것이 핵심! 그리고 개별로 접근할 때의 방식을 잘 기억해두자.