📔 이.코.테 Part2. BFS, DFS알고리즘 및 구현(Python)

README.MD

• 동빈나님의 '취코테를 위한 DFS, BFS' Youtube강의를 듣고 직접 실행해본 코드입니다
• Reference: https://www.youtube.com/watch?v=PqzyFDUnbrY&t=2712s
• -20.09.18.Fri. am 10:00 ~ 11:30

Steve-YJ/Colab_Exercise

---

DFS

• Depth-First-Search

  • 깊이 우선 탐색
  • 그래프에서 깊은 부분을 우선적으로 탐구하는 알고리즘입니다

• DFS 동작 과정은 다음과 같습니다

  • • 탐색의 시작노드를 스택에 삽입하고 방문 처리를 한다
    • 스택의 최상단 노드에 방문하지 않은 인접노드가 하나라도 있다면 그 노드를 스택에 넣고 방문 처리 한다방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다
    • 더이상 2번의 과정을 수행할 수 없을 때까지 반복한다

 

DFS 소스코드 예제(Python)

---

 

BFS

• BFS는 너비 우선 탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘입니다
• BFS는 큐 자료구조를 이용하며, 구체적인 동작 과정은 다음과 같습니다
  • • 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다
    • 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다
    • 더 이상 2번의 과정을 수행할 수 없을 떄까지 반복한다

DFS 소스코드 예제(Python)

 

 

DFS, BFS 비교

• 가장 큰 차이점
  • DFS는 Stack 자료구조를 사용한다
  • 반면 BFS는 Queue 자료구조를 사용한다

 

---

 

Appendix

01. Python 'If not' syntax

코테를 위한 Python 코드를 보면 유독 많이 등장하는 문법이 있습니다. 'If not' Syntax에 대해 간단하게 살펴봅니다.

 

What does 'if not' try to say? 

Reference: https://stackoverflow.com/questions/16739555/python-if-not-syntax

 

Answer

• There are subtle difference between if bar is not None and If not bar

• if not bar: will execute if bar is any kind of zero or empty container, or False

• Many people do use not bar where they really do mean bar is not None

=> 'if not bar'를 하게 되면 0이나 콘테이너의 값이 볐을 때 또는 False일지라도 코드가 실행된다고 합니다

=> 대부분의 Python Coder들은 'bar is not None'일 떄 'if not bat'문법을 사용한다고 합니다

 

02. Python not operator example with if statement

• Reference: https://www.jquery-az.com/4-demos-python-if-not-and-not-in-operator/

Comment

• As x>10 is False, so not operator evaluated as True
  • x>10 == False -> not False -> True
• Thus the if statement is True and code inside the if statement executed.

=> 이렇게 생각하면 좀 더 쉽게 이해가 되는 것 같습니다

=> 위의 예제에서 x > 10은 False입니다. 여기에 not이 붙으면 True가 되죠?
=> 따라서 if True가 되기 때문에 if문이 실행되는 것입니다.