[알고리즘] DFS (깊이 우선 탐색)

강의 출처 : 나동빈님 유튜브 강의

1. DFS (Depth-First Search) : 깊이 우선 탐색

• DFS는 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
• DFS는 스택 자료구조(혹은 재귀함수)를 이용하며, 구체적 동작과정은 다음과 같음
• 탐색시작노드를 스택에 삽입하고 방문 처리
• 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면, 그 노드를 스택에 넣고 방문처리
• 방문하지 않은 인접노드가 없으면(모두 방문했으면) 스택에서 최상단 노드를 꺼냄
• 더 이상 2번의 과정을 수행할 수 없을 때까지 반복

---

1-1. DFS 동작 예시 (예시는 번호가 낮은 인접 노드 부터 방문)

• [step 0] 그래프 준비 (방문 기준 : 번호가 낮은 인접노드부터) / 시작노드 : 1
  

---

• [step 1] 시작노드인 ‘1’을 스택에 삽입하고 방문처리
  

---

• [step 2] 스택의 최상단 노드인 ‘1’에 방문하지 않은 인접노드 ‘2’, ‘3’, ‘8’,이 있음
  이 중에서 가장 작은 노드인 ‘2’를 스택에 넣고 방문처리
  

---

• [step 3] 스택의 최상단 노드인 ‘2’에 방문하지 않은 인접노드 ‘7’이 있음
  따라서, ‘7’번 노드를 스택에 넣고 방문처리
  

---

• [step 4] 스택의 최상단 노드인 ‘7’에 방문하지 않은 인접노드 ‘6’, ‘8’이 있음
  이 중에서 가장 작은 노드 ‘6’번 노드를 스택에 넣고 방문처리
  

---

• [step 5] 스택의 최상단 노드인 ‘6’에 방문하지 않은 인접노드가 없음
  따라서 스택에서 6번 노드를 꺼냄
  

---

• [step 6] 스택의 최상단 노드인 ‘7’에 방문하지 않은 인접노드 ‘8’이 있음
  따라서 ‘8’번 노드를 스택에 넣고 방문처리
  

---

• 이런 과정을 반복했을 때, 전체 노드의 탐색순서 (스택에 들어간 순서)는 다음과 같음
• 탐색 순서 : 1 → 2 → 7→ 6 → 8 →3→ 4→ 5
  

1-2. DFS 소스코드 예제

# 각 노드가 연결된 정보를 표현 (2차원 리스트)
graph =[
		#0 [],
		#1 [2,3,8],
		#2 [1,7],
		#3 [1,4,5],
		#4 [3,5],
		#5 [3,4],
		#6 [7],
		#7 [2,6,8],
		#8 [1,7]
]

# 각 노드가 방문된 정보를 표현(1차원 리스트)
visited = [False] * 9
# False = 한 번도 인접하지 않는 것으로 초기화

# 정의된 DFS 함수 호출
dfs(graph, 1, visited)

---

# DFS 메서드 정의
# v = 인덱스로 해석됨
def dfs(graph, v, visited):
	# 현재 노드 방문처리
	visited[v] = True
print(v, end=' ')

# 현재노드와 연결된
# 다른 노드를 재귀적 방문
for i in graph[v]:
	if not visited[i]:
	# visited[v] = True가 아니면
		dfs(graph, i, visited)

>>> 1 2 7 6 8 3 4 5

---

2. 문제풀이 : 음료수 얼려먹기

N x M 크기의 얼음 틀이 있다.
구멍이 뚫려있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우, 서로 연결 돼 있는 것으로 간주한다.

이 때, 얼음 틀의 모양이 주어졌을 때, 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성해라. 다음의 4 x 5 얼음 틀 예시에서는 아이스크림이 총 3개 생성된다.

💡 DFS를 활용하는 알고리즘은 다음과 같다.
1. 특정지점의 주변 상,하,좌,우를 살펴본 뒤 주변 지점 중에서 값이 0이면서 아직 방문하지 않은 지점이 있으면 방문
2. 방문한 지점에서 다시 상,하,좌,우를 살펴본 뒤 방문을 진행하는 과정을 반복하면, 연결된 모든 지점을 방문 가능
3. 모든 노드에 대해 1~2번의 과정을 반복하며, 방문하지 않은 지점의 수를 카운트

💡 Cording

# 그래프 가로 세로 입력
N, M = map(int, input().split())
-------------------------------------------------------------------------------------
# (▼예시) : 그래프 입력 N번의 row 입력
# 2, 3
# 0 1 1
# 0 0 1
graph=[]
for i in range(N):
  graph.append(list(map(int,input().split())))
-------------------------------------------------------------------------------------
def dfs(x, y) :
  # 그래프 범위를 벗어났으므로 False
  if x <= -1 or x >= n or y <= -1 or y >=n :
    return False
-------------------------------------------------------------------------------------
	# 그래프 x,y좌표가 0이면, 1로 바꿔준다.
	# 그리고 상, 하, 좌, 우를 살펴보며 1로 바꿔준다.
	# 어차피 한 덩어리를 cnt +=1 하기 때문에 1개만 0이어도 cnt된다.
  if graph[x][y] == 0:
    graph[x][y] = 1
    # 상, 하, 좌, 우 좌표를 살펴본다.
    dfs(x-1, y) #상
    dfs(x+1, y) #하
    dfs(x, y-1) #좌
    dfs(x, y+1) #우
    return True
-------------------------------------------------------------------------------------
	return False # 0이 아니면 False
-------------------------------------------------------------------------------------
# 💡Tip: def 함수가 앞에 있어야 호출이 가능함
# 모든 좌표를 살펴보며, dfs가 True이면 cnt+=1
cnt = 0
for i in range(N):
  for j in range(M):
    if dfs(i,j) == True:
      cnt += 1
-------------------------------------------------------------------------------------
print(cnt)

---

• DFS 문제풀이 연상과정

1. 그래프 입력 범위 : n by m
2. 그래프 입력 : row 하나씩
3. for문으로 순차적인 그래프 좌표이동 구현
4. dfs 함수 구현

---