[ 동빈북 ] DFS/BFS- 음료수 얼려먹기

문제 해설

N*M 크기의 얼음틀이 있을때 구멍은 0, 칸막이는 1이라 한다. 구멍이 뚫려있는 부분끼리 상하좌우로 붙어 서로 연결되는 것으로 간주한다. 얼음틀의 모양이 주어졌을때 생성되는 총 아이스크림의 개수는?

IN
세로길이 N 가로길이 M
N+1줄까지 얼음틀의 형태

OUT
한번에 만들 수 있는 아이스크림의 개수

코드

n, m = map(int, input().split())
graph = []
for i in range(n):
    graph.append(list(map(int, input())))

def dfs(x, y):
	#범위 검사
    if x<0 or x>=n or y<0 or y>=m:
        return False
    if graph[x][y] == 0:
    	#방문하지 않은 노드에 대해
        graph[x][y] = 1
        #print(x, y, graph[x][y])
        #상하좌우 재귀적으로
        dfs(x-1, y)
        dfs(x, y-1)
        dfs(x+1, y)
        dfs(x, y+1)
        return True
    return False

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