음료수 얼려먹기 - DFS (2021/02/22)

이 문제는 NxM의 얼음틀에서 0끼리 뭉쳐 있는 부분의 개수를 구하는 문제다.

 

예를들어

00110
00011
11111
00000

이 주어지면 0끼리만 뭉쳐있는 부분이 세군데이므로 3을 출력한다.

 

DFS를 이용하여 0인 부분을 방문하고 1로 바꾼다. 그리고 재귀함수를 이용해 DFS를 상하좌우로 반복한 후, True를 반환한다.

 

그리고 main문에서 dfs가 True인 개수를 세면 

 

 

1. (0,0)이 0이었기 때문에 dfs함수에 의해 1로 바뀌고 상하좌우의 0도 1로 바뀐다. 그리고 True를 반환하여 main문에서 count한다.

2. 1의 과정을 통해 0끼리 뭉쳐있는 부분은 이미 1로 바뀌었고 총 세군데를 방문하여 3이 출력된다.

 

코드로 나타내면

 

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


graph=[]
for i in range(n):
    graph.append(list(map(int,input())))
    
001
010
101



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,y-1)
        dfs(x+1,y)
        dfs(x,y+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)


3