[DFS] 음료수 얼려 먹기

- 문제

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

 

ex)

00110

00011

11111

00000  

-> 아이스크림 3개 생성

 

- 해설

DFS 로 해결할 수 있는 문제

1. 특정한 지점의 주변 상하좌우를 살펴본 뒤에 주변 지점 중에서 값이 0 이면서 아직 방문하지 않은 지점이 있다면 해당 지점을 방문

2. 방문한 지점에서 다시 상하좌우를 살펴보면서 방문을 다시 진행하면 연결된 모든 지점을 방문할 수 있다.

3. 1~2번의 과정을 모든 노드에 반복하며 방문하지 않은 지점의 수를 센다.

 

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

# 2차원 리스트의 맵 정보 입력받기
graph =[]
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+1,y)
        dfs(x,y-1) 
        dfs(x,y+1)
        # 범위 벗어나면 False 뜰거고 상하좌우 연결된 곳까지 다보고 나면 True 출력
        # 연결된 좌표는 전부 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)