음료수 얼려 먹기(DFS/BFS)

문제

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

00110
00011
11111
00000

입력 

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

출력

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

풀이

• 입력 받기
•  현재 위치에서 상하좌우를 탐색(BFS/DFS) 
•  탐색 한 곳의 값이 0이고, 아직까지 방문하지 않았다면 계속 해서 상하좌우를 탐색한다.
•  탐색을 마쳤다면, 생성되는 아이스크림의 값을 1 더해준다.
•  이 과정들을 반복하여 한 번에 만들 수 있는 아이스크림의 개수를 출력한다.

코드

# 세로길이 N, 가로길이 M
n, m = map(int,input().split())
graph = []
for _ in range(n):
    graph.append(list(map(int,input())))

def dfs(y,x):
    # 범위 벗어 날 경우 종료 (재귀 종료조건)
    if y <= -1 or y >= n or x <= -1 or x >= m:
        return False
    # 현재 그래프의 값이 0인경우, 재귀적으로 상하좌우 탐색
    if graph[y][x] == 0:
        graph[y][x] = 1
        dfs(y - 1, x)
        dfs(y + 1, x)
        dfs(y, x - 1)
        dfs(y, x + 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)