hmk run dev

잡다한 글 DFS 본문

Algorithm

잡다한 글 DFS

hmk run dev 2021. 3. 11. 19:28

#################
# 1을 방문했을 때 2,5,9를 스택에 넣어준다
# 맨처

# 위의 그래프를 예시로 삼아서 인접 리스트 방식으로 표현했습니다!
graph = {
1: [2, 5, 9],
2: [1, 3],
3: [2, 4],
4: [3],
5: [1, 6, 8],
6: [5, 7],
7: [6],
8: [5],
9: [1, 10],
10: [9]
}



# 1. 루트 노드를 스택에 넣는다.
# 2. 현재 스택의 노드를 빼서 visited에 추가한다
# 3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 스택에 추가한다.
# 4. 2부터 반복한다
# 5. 스택이 비면 탐색을 종료한다

def dfs_stack(adjacent_graph, start_node): #그래프, 노드
stack = [start_node] # 1
visited = [] # 맨처음엔 1이 들어온다

while stack: # 스택이 비어있을때 까지
current_node = stack.pop() # 맨 뒤에껄 팝 한걸 비지트에 계속 넣어준다
visited.append(current_node) # visited = [1] 스택의 마지막 값을 어팬드 해준다계쏙쏙
for adjacent_node in adjacent_graph[current_node]: # 그래프의 마지막값을 빼준게 레인지 한번 빼주고 돌리고 빼주고 돌리고
if adjacent_node not in visited: # 비지트 않에 겹치는 요소가 없을 경우에 // 있다면 그냥 팝하겠죠?
stack.append(adjacent_node) # 스택에 넣어준다 요소를 그리고 위에서 팝을 해준 값을 비지트에 어펜드

return visited

print(dfs_stack(graph, 1)) # 1 이 시작노드입니다!

 


DFS 코드 해설

 

그래프(표)와 스타트 노드를 입력값으로 받아준다

 

stack = 스타트 노드(1)가들어있는 정렬로 만들어준다

visited 정렬 = [] 비어있는 정렬로 만들어준다

 

스택이 비어있을때 까지 while문을 돌려준다

while stack: > 이렇게 써주면 같은 의미이다

 

이때 current_node 라는 변수에 stack.pop()이라는 코드를 부여해준다

이것은 맨뒤에있는 정렬을 빼낸다는 의미다

 

그리고 visited에 append / current_node 를 해준다 이 의미는 

스택의 마지막 요소를 때줌과 동시에 비지트에 어펜드 해준다는 의미로 해석했다

 

그리고 반복문을 돌려준다 

for adjacent_node in adjacent_graph[current_node]:

 

여기서 햇갈리는데 adjacent_graph[current_node] 입력값으로 받은 그래프의 

마지막 요소를 pop한 값 즉 정렬의 마지막 값이라고 보면된다?

 

그리고 그것을 adjacent_node 로 반복시켜서 하나씩 검사한다

 

단순한 반복이 아닌 조건문을 붙여서 반복시키는데

 

조건문을 살펴보면 

 

if adjacent_node not in visited:

 

비지트 정렬에 adjacent_node(그래프의 마지막값을 pop한 것)이 없다면

 

stack.append(adjacent_node) 스택에 팝한 값을 넣어줘라 

 

이렇게 하면 계속 돌고돌아서 stack 정렬은 결국 비어 있게 되고 visit는 겹치는것 없이

 

정렬이 완성된다


요약하자면 

 

1.  스택에 스타트 노드 => 트리의 가장 위엣값을 넣어준다

 

2. visited 빈 정렬을 만들어준다

 

3. 스택 정렬이 빈 정렬이 될때까지 while문을 실행

 

4. 스택 pop을 변수로 지정해서 스택을 비워줌과 동시에 visited에 변수를 넣어준다

 

5. 조건문으로 visited에 있는 것은 넣지 않고 반환한다

 

6. 결국 입력값으로 넣어준 그래프를 계속 돌리면서 겹치는 것은 넣지않고 새로운 것은 

   넣어주면된다 그리고 visited를 리턴 값으로 주면 완료!

 

'Algorithm' 카테고리의 다른 글

백준 28258 큐 2  (0) 2021.03.16
백준 4948 베르트랑 공준 풀이  (0) 2021.03.13
DFS & BFS  (0) 2021.03.11
Comments