음료수 얼려먹기

💻 입력 조건

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

💻 출력 조건

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

💻 입력 예시

15 14
00000111100000
11111101111110
11011101101110
11011101100000
11011111111111
11011111111100
11000000011111
01111111111111
00000000011111
01111111111000
00011111111000
00000001111000
11111111110011
11100011111111
11100011111111

💻 출력 예시

8

📖 문제 해결
dfs 알고리즘을 이용하여 재귀적으로 '덩어리'의 시작점을 찾아 얼리기 시작한 후 '덩어리'전체를 얼려나가는 코드입니다. 구멍 하나의 입장에서 상하좌우 중 한 지점이라도 다른 구멍과 연결되어 있으면, 연결되어 있는 구멍들끼리 '덩어리'로 생각하게 되는 개념에 집중하여 생각해보면 해답을 생각해낼 수 있는 문제 같습니다. 개인적으로는 디버깅을 위해 show_graph()함수를 따로 작성하여 확인하였습니다.

# n과 m의 정보 입력 받기
n, m = list(map(int, input().split()))

# 2차원 리스트 정보 입력 받기
graph = []

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

# freezepop()은 얼려지지 않은 '덩어리'를 찾아 얼려나가는 함수
def freezepop(graph,r,c):
    
    # 얼려지지 않은 부분이 있다면
    if graph[r][c] == 0:
        
        # 얼리기
        graph[r][c] = 1
        
        # 상하좌우에 얼려지지 않은 부분이 있다면 찾아서 얼리기
        if r-1 >= 0 :
            freezepop(graph,r-1,c)
        if r+1 <= n-1 :
            freezepop(graph,r+1,c)
        if c-1 >= 0:
            freezepop(graph,r,c-1)
        if c+1 <= m-1:
            freezepop(graph,r,c+1)
            
        # 여기까지 수행을 하고 나면, 함수 내에서 재귀적으로 주위의 얼려지지 않은 부분을 찾아 얼려 나가므로
        # 찾은 덩어리 전체를 얼리는 것과 같음
        
        return True

count = 0
for r in range(n):
    for c in range(m):
        if freezepop(graph,r,c) == True:
            count += 1

print(count)

# 코드 디버깅을 위한 함수
def show_graph(graph):
    for r in graph:
        print(r)