DFS 는 깊이우선 탐색 방식이다.
1. 구현 방법
1-1. 스택
1-2. 재귀 << 더 많이 쓴다. 사실 재귀를 쓰는게 컴퓨터 구조적으로 스택을 이용하는거기 때문에 원리는 똑같다.
DFS 도 완전탐색의 일종이기에, 모든 노드를 다 살펴본다.
인접 행렬로 구현한다하면 adjacent, 줄여서 adj 배열을 하나 선언해서 쓴다. 2차원 배열 형태가 될 것이다.
adj = [[0] * 13 for _ in range(13)] #[0, 0 , ...0] 이 13 줄인 인접 행렬이 생성됨.
#수동으로 넣는 상황이라면
adj[0][1] = adj[0][7] = 1 # 이런식으로 0에서 1로 가는 간선, 0에서 7로 가는 간선.. 이런 식으로하면 됨.
def dfs(now): # 현재 방문한 노드에 대해 할 작업
for nxt in range(13): # 현재 방문한 노드와 다른 나머지 노드들간의 관계를 확인해본다.
if adj[now][nxt]: # 만약 간선이 있다면,
dfs(nxt) # 다음 노드로 탐색을 진행한다. 다음 노드가 현재 노드가 되어 탐색이 진행된다.
# 이렇게 되면, 연결된 다른 노드에 접근하는 상황은 지금 당장 이루어지지 않고, 스택 형태로 쌓이게 된다.
#처음 노드
def(0)