[Algorithm] 깊이 우선 탐색(DFS), 넓이 우선 탐색(BFS)

✨깊이 우선 탐색(DFS, Depth First Search)

시작 노드에서 자식의 노드들을 순서대로 탐색하면서 깊이를 우선으로 탐색하는 알고리즘

 

 

 

 

 

ex)백준 알고리즘 수업 - 깊이 우선 탐색 2 

https://www.acmicpc.net/problem/24480

import sys
from collections import deque

visited=[]


need_visit=deque()

N,M,R=map(int,sys.stdin.readline().rstrip().split(" "))
visited_dic={i:0 for i in range(1,N+1,1)}
graph={i:[] for i in range(1,N+1,1)}

#무방향이므로 a,b 서로의 인접노드 추가
for i in range(M):
    a,b=map(int,sys.stdin.readline().rstrip().split(" "))
    graph[a].append(b)
    graph[b].append(a)


need_visit.append(R) #시작노드 설정
number=1

while True:
    n=need_visit.pop()#이번 탐색노드 n pop
    
    if(visited_dic[n]==0): #n이 이미 탐색한 노드가 아니면
        visited_dic[n]=number #n은 number순서로 방문함
        number+=1			#number 순서 +1
        qq=list(graph[n])	#인접노드를 리스트로
        #인접노드를 오름차순 정렬(DFS 이므로 이러면 내림차순으로 pop된다)
        qq.sort()			
        need_visit.extend(qq)#인접노드를 탐색할 목록에 추가
    
    if(not need_visit):break	#남은 노드없으면 끝

for i in range(1,N+1,1):
    sys.stdout.write(str(visited_dic[i])+"\n")

 

 

 

 

 

✨넓이 우선 탐색(BFS, Breadth first search)

루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법

 

 

 

 

 

 

 

 

ex) 백준 알고리즘 수업 - 너비 우선 탐색 1

import sys
from collections import deque

visited=[]


need_visit=deque()

N,M,R=map(int,sys.stdin.readline().rstrip().split(" "))
visited_dic={i:0 for i in range(1,N+1,1)}
graph={i:[] for i in range(1,N+1,1)}

#무방향이므로 a,b 서로의 인접노드 추가
for i in range(M):
    a,b=map(int,sys.stdin.readline().rstrip().split(" "))
    graph[a].append(b)
    graph[b].append(a)


need_visit.append(R) #시작노드 설정
number=1

while True:
    n=need_visit.pop()#이번 탐색노드 n leftpop(BFS이므로)
    
    if(visited_dic[n]==0): #n이 이미 탐색한 노드가 아니면
        visited_dic[n]=number #n은 number순서로 방문함
        number+=1			#number 순서 +1
        qq=list(graph[n])	#인접노드를 리스트로
        			
        #인접노드를 오름차순 정렬(BFS이므로 오름차순으로 leftpop 될것이다.)
        qq.sort()
        need_visit.extend(qq)#인접노드를 탐색할 목록에 추가
    
    if(not need_visit):break	#남은 노드없으면 끝

for i in range(1,N+1,1):
    sys.stdout.write(str(visited_dic[i])+"\n")

 

 

 

 

 

 

 

 

 

 

 

 

🎈참고자료

https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html

https://data-marketing-bk.tistory.com/entry/DFS-%EC%99%84%EB%B2%BD-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0-%ED%8C%8C%EC%9D%B4%EC%8D%AC