DFS - 음료수 얼려먹기

DFS (Depth First Search)

DFS, 깊이 우선 탐색이란 그래프에서 가장 깊이 있는 노드부터 탐색하는 알고리즘이다.

일반적으로 stack 자료구조와 재귀함수를 통해 구현할 수 있다. 

 

음료수 얼려 먹기

이코테에서 DFS 대표 문제로 '음료수 얼려 먹기' 문제가 있다. 

N X M 크기의 얼음 틀이 있을때, 음료를 담을 수 있는 칸은 0으로, 막힌 칸은 1로 표시가 되어있다.

그래서 틀의 모양에 따라 몇 덩이의 얼음 덩어리가 나오는지 세는 문제이다. 

 

[input]
1. n(세로길이) 과 m(가로길이)가 띄어쓰기로 입력 된다.
2. n X m 의 2차원 리스트가 한줄씩 0과 1로 입력된다.
ex)
001
010
101

[output]
구할 수 있는 얼음 덩어리의 개수

이 문제가 왜 DFS 문제일까? 🤔

그래프에서 0은 서로 이어져있어서 방문할 수 있는 노드, 1은 방문할 수 없는 노드라고 생각하고

'하나의 노드에서 이어져있는 모든 노드를 방문한다' 고 생각하면 되기 때문에 DFS로 풀 수 있는 것이다.

 

답안 코드

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

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

def dfs(x, y)
	# x와 y가 2차원 리스트의 범위 밖이라면 return False
	if not 0 <= x < n or not 0 <= y < m:
    	print(graph)
    	return False
    
    # 해당 노드가 0이라면 1로 방문표시하고, 해당 노드의 상하좌우 모두 재귀적으로 확인
    if graph[x][y] == 0:
    	graph[x][y] = 1
        print(graph)
        dfs(x-1, y)
        dfs(x, y-1)
        dfs(x+1, y)
        dfs(x, y+1)
        return True
        
    # 해당 노드가 1이라서 방문할 수 없다면 return False
    print(graph)
    return False
    
    answer = 0
    
    for i in range(n):
    	for j in range(m):
       		print(f'i: {i}, j: {j}')
    		print(dfs(i, j))
        	# 그래프의 (0, 0)부터 (n, m)까지 dfs 함수 실행하고 값이 True인 경우만 카운트
        	if dfs(i, j) == True:
            	answer += 1

책에서 답안 코드를 보고도 이해가 잘 되지 않는 부분이 있었다. 

 

• 시작 노드의 상하좌우 노드들을 확인하기 위해 재귀적으로 dfs 함수를 호출할때 return 되는 값은 영향을 안미치는가?

➡️ 유튜브에서 해설을 찾아보니까 답을 얻을 수 있었다. 해당 부분에서의 return 값은 따로 사용하지 않고, 단순히 시작점에서 연결된 0을 1로 바꿔주기만 한다.

---

• 재귀적으로 dfs 함수를 호출하는 부분에서 그래프가 어떻게 바뀌는가?

➡️ 이 부분을 확인하기 위해 return이 되는 경우가 세 가지가 있고 각각 graph를 프린트하여 확인해 보았다.

아래 사진은 graph가 위의 예시처럼 입력 되었을 때의 출력문이다. [[0,0,1], [0,1,0], [1,0,1]]

for 문에서 그래프의 (0,0)부터 (n,m)까지 노드들에 대해 dfs 함수를 실행 시킬때, 노드의 위치인 i와 j값과 return 값을 함께 출력했다.

처음 시작인 (0,0)이 0이었기 때문에 1로 바뀐것이 그래프 출력문 중 첫 줄의 [[1,0,1], [0,1,0], [1,0,1]] 이다.

 

그러고 나서 (0,0) 을 기준으로 상하좌우를 확인하기 위해 dfs 함수가 네 번 더 호출되는데, (0,0)의 아래인 (x+1, y) 즉, (1,0)을 확인했을때 그 값이 0이므로 해당 위치를 1로 바꿔서 그래프의 모습이 한번 더 바뀐다.

그게 그래프 출력문 중 넷째 줄인 [[1,0,1], [1,1,0], [1,0,1]] 이다. 

 

이 시점부터는 (1, 0)을 기준으로 재귀함수들을 모두 호출한 뒤 다시 원래 기준이었던 (0,0)으로 돌아와서 실행하지 못한 나머지 재귀함수를 마저 호출한다. 

---

• for 문에서 dfs를 실행한 결과가 True 인 경우만 count하는게 무슨 의미인가?

➡️ (0,0)부터 (n,m)까지 모두 dfs를 실행하고, 그 중 값이 0인 위치에서만 유일하게 재귀함수들 호출과 True가 return 된다. 

즉, 일단 0을 감지한 순간 그 0과 연결된 모든 0들을 다 확인한 다음에 True를 반환하기 때문에 0을 1로 바꾸는 코드가 실행될 때만 카운트를 하면 덩어리의 개수를 셀 수 있는 것이다.