[파이썬]DFS 음료수 얼려먹기

음료수 얼려 먹기

문제

N × M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다.
구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다.
이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하라.
다음의 4 × 5 얼음 틀 예시에서는 아이스크림이 총 3개가 생성된다

입력

• 첫 번째 줄에 얼음 틀의 세로 길이 N과 가로 길이 M이 주어진다. (1 <= N, M <= 1,000)
• 두 번째 줄부터 N + 1 번째 줄까지 얼음 틀의 형태가 주어진다.
• 이때 구멍이 뚫려있는 부분은 0, 그렇지 않은 부분은 1이다.

출력

한 번에 만들 수 있는 아이스크림의 개수를 출력한다.

입력 예시 1

4 5

00110

00011

11111

00000

출력 예시 1

3

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

graph = []
result = 0

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

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

for i in range(n):
    for j in range(m):
        
        if dfs(i,j) == True:
            result += 1

• '0'인 값이 상하좌우로 연결되어 있는 노드를 묶자
• 모든 노드를 돌며 상하좌우에 0이 있는지 찾는다 0이 있는 구역의 첫 노드값에 도착했을때 return True 하고 dfs함수를 이용하여 주변 0을 1로 만들어준다. (return 값을 활용하지 않기 때문에 함수의 역할은 0인 노드를 1로 바꾸는것 뿐) 

• #공백 없이 입력되는 숫자를 하나씩 리스트에 넣고 그 리스트를 한줄씩 빈 리스트에 붙이면 이중리스트가 된다 
  graph = []
  for i in range(n):
      graph.append(list(map(int,input())))