알고리즘 이론 :: DFS/BFS

구현 코드 출처는 이코테!

---

 

DFS

 

구현 코드

# DFS

def dfs(st):
        visited[st]=True
        print(st,end=' ')
        
        for i in graph[st]:
            if not visited[i]:
                dfs(i)
graph=[
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]
           
# 각 노드가 방문된 정보 초기화
visited=[False]*9

#정의된 dfs 함수 호출
dfs(1) # 1부터 시작

 

 

BFS

 

 

구현 코드

# BFS
from collections import deque
def bfs(st):
    qu=deque([st]) #덱 
    visited[st]=True
    
    while qu: #큐가 빌때까지
        v=qu.popleft() # 시작 뽑기
        print(v,end=' ')
        
        for i in graph[v]:
            if not visited[i]:
                qu.append(i) # 방문하지 않은 곳 큐에 추가
                visited[i]=True    
                
graph=[
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]


visited=[False]*9 # 방문위치 초기화
bfs(1)

 

• 주로 bfs에서 queue 대신 deque를 많이 쓰던데 이런 이유 때문인 것 같다!

 

https://www.acmicpc.net/board/view/49166

글 읽기 - [파이썬] deque구현과 queue구현의 차이점

 

 

그럼 언제 DFS/BFS를 사용하는가?

DFS

• 그래프의 모든 정점 방문
• 경로 특징 있을 경우
• 재귀 호출해야하는 문제

BFS

• 그래프의 모든 정점 방문
• 최단거리(최소횟수) 구하기(미로탐색)

 

...라고 나오는데 관련 문제 풀면서 감을 잡아야겠다

 

---

참고 영상&글

 

 

https://www.youtube.com/watch?v=_hxFgg7TLZQ&t=232s 

 

https://foameraserblue.tistory.com/188?category=481823 

PS를 하며 느끼는 DFS와 BFS 선택의 기준

---

DFS/BFS 기초 문제 (계속 추가..)

기초 문제
DFS와 BFS - 실버 2	https://www.acmicpc.net/problem/1260
깊이우선 탐색 1 - 실버 2	https://www.acmicpc.net/problem/24479
깊이 우선탐색 2 - 실버 2	https://www.acmicpc.net/problem/24480