[샛길공부] DFS와 BFS (feat. 이코테 유튜브강의)

 

백준 문제를 풀다가 갑자기 처음보는 모르는 단어를 마주치면서 시작한 공부

문제 풀기는 아래 참고 👇👇👇

https://coding-nurse.tistory.com/21?category=975166 

 

---

* 강의 채널 : 동빈나

* 강의 이름 : (이코테 2021 강의 몰아보기) 3. DFS & BFS

* 강의 링크 : https://youtu.be/7C9RgOcvkvo 

---

 ❗ 스택& 큐 / 재귀함수

*스택(STACK) : 먼저 넣는 것 가장 아래, 빼낼 때 가장 나중 것 like 박스안에 넣는 것

*큐(QUE) : 먼저 넣는 것 뺄 때도 먼저 나옴 like 터널 

 

*재귀 함수: 자기자신을 다시 호출하는 함수

- 무한히 문자 출력가능. 파이썬은 오류 발생

- 조건을 주어서 무한 호출 제한을 둔다

      😁 내 나름 재귀함수 예제 만들어보기 ㅋㅋㅋ

def sona(x):
    if x==6:
        return
    print(x,'번 뽀뽀를 했습니다 ^ 3^')
    sona(x+1)
    print(x,'번 입을 닦았습니다ㅋㅋㅋ')
    
sona(1)

#  유클리드 호제법 : 두 자연수 A,B(A>B)에서 A%B==R이면, 
#  A와B의 최대공약수는 B와R의 최대공약수와 동일 
 
def gcd(a,b):
    if a%b==0:
        return b
    else:
        return gcd(b, a%b)
 
print(gcd(18,15)) ---> 3

---

 ❗ DFS

깊이 우선 탐색. 깊은 부분을 우선적으로 탐색하는 알고리즘. 스택 자료구조(혹은 재귀함수)를 이용

🎃 동작 과정
1) 탐색시작 노드를 스택에 삽입하고 방문처리를 합니다.
2) 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라고 있으면 그 노드를 스택에 넣고 방문 처리합니다.
만약 방문하지 않은 인접 노드가 없으면 스탭에서 최상단 노드를 꺼냅니다.
3) 더 이상 2)번의 과정을 수행할 수 없을 때 까지 반복합니다.

---

 ❗ BFS

너비우선 탐색. 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘. 큐자료구조

특정조건에서 최단경로 문제에서 자주 사용 

🎃 동작 과정
1) 탐색시작 노드를 큐에 삽입하고 방문 처리를 합니다.
2) 큐에서 노드를 꺼낸 뒤 해당 노드의 인접노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리합니다.
3) 더이상 2번의 과정을 수행할 수 없을 때까지 반복합니다.

---

🧐공부 한줄 평 : 처음 보는 개념은 관련 문제 많이 풀어봐야 안 까먹으니 얼른 풀어봐야지!