[기초 알고리즘1/탐색] DFS / BFS

210111

 

새로운곳에 취직을 하게 되었다.

이번에 이직을 하면서 느낀점은 아직 내게 기본기가 탄탄히 갖춰져 있지 않다는 것 😢

다시 초심으로 돌아가 원하는 꿈을 위해 천천히 성장해야 겠다는 다짐을 다시한번했다

 

이 두가지 탐색 알고리즘은 너무 유명하고 기초적인 알고리즘이라 자세한 설명은 하지 않겠다.

(게으름)

 

 

 

 

Step. 1 용어

구현에 필요한 용어들이다.

 

DFS : Depth First Search Algorithm

BFS : Breadth First Search Algorithm

(*노드기준)

 

Stack : Last In Frist Out

Queue : Fisrt In First Out

 

위 알고리즘들은 각각 이렇게 사용된다.

DFS	Stack
BFS	Queue

 

 

Step. 2 구현

각각의 구현에 필요한 그래프 초기화

graph = {
'A': ['B'],
'B': ['A', 'C', 'H'],
'C': ['B', 'D'],
'D': ['C', 'E', 'G'],
'E': ['D', 'F'],
'F': ['E'],
'G': ['D'],
'H': ['B', 'I', 'J', 'M'],
'I': ['H'],
'J': ['H', 'K'],
'K': ['J', 'L'],
'L': ['K'],
'M': ['H']
}

graph는 Dictionary 형태로 구현한다. 그래프 분석을 잠깐해보자

 

1. Every keys are Parents

2. Every values are Children except the first value from the second index. 

*All rules are applied except the first node

 

2번 규칙때문에 아래 여러가지 조건문이 생겼다.

 

 

DFS 구현

###############초기화 부분##################

1. first_node = list(graph.keys())[0] #첫번째 노드를 가지고 온다

2. stack = [] #노드 탐색을 위해 중간중간 저장에 필요할때 사용할 리스트
3. value = '-1' #노드 탐색을 위해 중간중간 저장에 필요할때 사용할 empty variable

4. answer = [first_node] #탐색한 노드를 순서대로 저장할 리스트

##########################################

변수가 사용되는 구조가 아래와 같다.

graph -> stack(이 변수에서 작업) -> answer 

 

이 알고리즘에서는 두가지를 출력할수 있다.

노드가 탐색된 순서와 원하는 노드가 있을때 몇번째에 발견되는지 위치이다.

 

정답화면

 

############### 첫번째 노드 처리 부분 ###############

stack.append(first_node) #첫번째 노드를 넣어준다

#첫번째 노드의 자식들을 스택에 넣어준다
(1)reverse_childeren = list(reversed(graph[first_node]))
for i in range(0,len(graph[first_node])) : 
    stack.append(graph[first_node][i]) 

##########################################

(1)번 부분에서 reversed를 사용한 이유는 A,B,C,D의 순서로 이어져 있을때 스택에 이 순서대로 넣으면 맨 오른쪽 부터 빠지기 때문이다. 왼쪽부터 빠져야 왼->오 순서로 탐색을 할수가 있는데 Stack은 맨 마지막에 있는게 먼저 바지는 구조이기 때문에 불가능하다.

 

그래서 뒤집어서 오른쪽에 있는 노드들 부터 먼저 넣어서 왼쪽에 있는 노드부터 하나씩 탐색하는 방식으로 구현했다.

 

 

 

 

###############DFS Algorithm###############

while len(graph) != len(answer)-1 : 
#정답 리스트의 길이가 주어진 그래프의 길이와 같아질때 까지 = 전부탐색할때까지

    value = stack.pop() #맨뒤에 있는걸 하나 빼서
    answer.append(value) #정답에 넣고

    if len(graph[value])==1 : #자식이 없으면 아래 자식을 스택에 추가할 필요가 없다
        continue 

    reverse_childeren = list(reversed(graph[value])) #자식이 있으면 아래 자식을 스택에 추가한다
    for i in range(0,len(reverse_childeren)-1) : 
        stack.append(reverse_childeren[i]) 

##########################################

 

 

 

 

 

BFS 구현

###############초기화 부분##################

1. first_node = list(graph.keys())[0] #첫번째 노드를 가지고 온다

2. queue = [] #노드 탐색을 위해 중간중간 저장에 필요할때 사용할 리스트
3. value = '-1' #노드 탐색을 위해 중간중간 저장에 필요할때 사용할 empty variable

4. answer = [first_node] #탐색한 노드를 순서대로 저장할 리스트

##########################################

변수가 사용되는 구조가 아래와 같다.

graph -> queue(이 변수에서 작업) -> answer 

 

DFS와 달라진 점은 Queue(퀘우웨우)를 사용한다는 점! DFS는 길이가 1인 노드들 한개 하고 그 뒤에 넣고 하는 작업이 반복적으로 진행되다 보니 뺐다 넣다 하는게 복잡했다. (하나 넣고 기다려야 하는 느낌?!)

-> 계속해서 깊게 파야 하므로 자식부터 빠짐

 

BFS는 하나 넣고 자식 노드들을 다 넣고 이제 넣은 순서대로 하나씩 빼면서 작업을 하면 되니 직관적으로 POP, APPEND를 실시할 수 있다.(넣고 바로 빼는 느낌?! 첫번째 노드를 넣으면 그 다음노드가 바로 빠진다!)

-> 만나는대로 빠지므로 부모부터 빠짐

 

 

 

 

############### 첫번째 노드 처리 부분 ###############

for i in range(0,len(graph[first_node])) :
    queue.append(graph[first_node][i])

##########################################

DFS와 다르게 복잡하게 생각할 필요 없다! 뒤에서부터 뺄필요 없고 걍 들어온대로 빼면 되니 그냥 넣으면 된다😁😁

 

 

 

 

 

###############BFS Algorithm###############

while len(graph) != len(answer) :  
#정답 리스트의 길이가 주어진 그래프의 길이와 같아질때 까지 = 전부탐색할때까지

    value = queue.pop() #맨앞에 있는걸 하나 빼서
    answer.append(value) #정답에 넣고

    if len(graph[value])==1 : #자식이 없으면 아래 자식을 큐에 추가할 필요가 없다
        continue 

    for i in range(1,len(graph[value])) : #자식이 있으면 아래 자식을 큐에 추가한다
        stack.append(graph[value][i]) 

##########################################

자식을 추가하는 부분만 살짝달라지고 BFS와 거의 같다. 여기서 더 발전된 알고리즘이 A*라고 하는데 그 부분도 한번 공부해보자.

 

 

 

 

 

 

STEP 3. 여담

Running time

DFS와 BFS는 Vertex를 방문하고 그 다음에 연결된 edge를 방문한다. 만약 A라는 Vertex에 2개의 edge가 그려져 있으면 적어도 두번은 방문하겠지? 그러므로 걸리는 시간은 O(V+E).

 

Queue 발음

큐 발음이 웃기다 ㅋㅋㅋ. 사람들이 가끔 왜 저 단어다 쿠웨우웨우가 아니냐고 주장하면 맞는 말 같아서 웃기다.

 

파이썬 최고

C로 구현했으면 링크드 리스트 각인데 Python덕분에 Dictionary구조로 합의봤다 ^^. 시간이 남으면 C#으로 구현해봐야겠다.

 

백준문제

BFS를 활용하는 백준문제 풀이 후 포스팅 링크를 남길 예정