음료수 얼려 먹기

문제

얼음틀 모양이 주어졌을 떄 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오.

입력

4 5
00110
00011
11111
00000

출력

3

풀이 방법

상하좌우가 연결되어있는 그래프라 보고
전체의 노드를 하나씩 돌아가면서 검사를 할 텐데
0이 노드를 만나면 일단 result를 증가시키고, dfs를 통해 연결된 모든 노드를 1로 변경한다.

DFS가 종료되면 다시 모든 노드를 순차탐색한다.

코드

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

graph = []
for i in range(n):
    graph.append(list(map(int, input())))
def dfs(graph, i, j):
    if i <= -1 or i > n-1 or j <= -1 or j > m-1:
        return    
    if graph[i][j] == 1:
        return
    graph[i][j] = 1    
    dfs(graph, i-1, j)
    dfs(graph, i+1, j)
    dfs(graph, i, j-1)
    dfs(graph, i, j+1)


result = 0
for i in range(n):
    for j in range(m):
        if graph[i][j] == 0:
            result+=1
            dfs(graph, i, j)

print(result)

느낀 점

graph.append(list(map(int, input()))) 할 때 input().split()이 아니라
input()이라는 걸 처음 알아챈 거 같다.

다른 부분은 크게 어렵지 않았다.