[DFS/BFS] 음료수 얼려먹기

출처 - [책] 이것이 코딩 테스트다. with python

문제

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

예시

input 

4 5
00110
00011
11111
00000

output
3

코드

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
        return 0
    if graph[x][y]==0:
        #print(x,y, end='\n')
        graph[x][y]=1
        dfs(x+1,y) 
        dfs(x-1,y) 
        dfs(x,y+1) 
        dfs(x,y-1) 
        return 1
    return 0    
   
answer =0

for i in range(n):
    for j in range(m):
            answer+=dfs(i,j)

print(answer)

💡아이디어

dfs함수 설명: 상하좌우를 모두 탐색하여 칸막이를 만날 때까지 탐색을 한다. 해당 노드를 방문했다는 표시로 노드의 값을 0에서 1로 바꾸어 더 이상 탐색하지 못하도록 한다. 연결된 모든 지점을 찾고 끝내면 1을 리턴하도록 한다.

종료조건 - graph[x][y]의 값이 1이거나 x,y의 범위가 배열의 인덱스를 벗어나는 경우 0을 리턴하도록 한다.

for문 설명: 예시 4*5배열을 이용해서 설명.
dfs함수에서 연결된 노드들을 찾고 1을 리턴하면 graph[n-1][m-1]까지 탐색하지 않고, (1,2)노드에서 탐색을 종료하게 된다.
그 다음 덩어리..를 찾기 위해서 이중 for문을 이용해서 순차적으로 탐색해서 아이스크림의 개수를 얻을 수 있도록 한다.