[알고리즘 개념 공부] DFS/BFS 파이썬으로 살펴보기

 

 

두둥!

 

지난 주말 2022 카카오 썸머 인턴십 코테를 봤다..

 

결과는 아직 나오지 않았지만,,

이미 부족함을 너무나도 느껴버렸다...!!

 

 

그중 가장 많이 느꼈던 건 

BFS.. 문제인 걸 알면서도 풀지 못하는 나... 😂😂😂😂

 

 

그래서 오늘 스터디에서는 문제를 푸는 것 대신에 개념을 공부하기로 했다!!!

 

 

 

 

 

---

 

 

 

 

 

BFS (Breadth First Search; 너비 우선 탐색)

 

• 최단 길이 경로를 보장
• 무한 그래프는 답이 안 나온다! BFS도 끝나지 않음!
• 가지가 많은 것은 DFS를 선택하는 것이 좋다!!
• queue 개념을 사용!! (cf. DFS는 stack 개념 사용)

 

---

 

기본적인 알고리즘은

 

👉 인접한 노드 중에서 방문하지 않았던 노드 정보만을 큐에 넣기! 먼저 있던 노드부터 방문!!

👉 FIFO인 queue 개념을 사용!!

 

 

 

 

---

 

Python을 사용해서 어떻게 구현하는지 살펴보자!!!

 

 

👍 먼저 첫 번째, List 타입을 사용하는 방법이 있다!!

 

list.append(1) # 인접행렬에 대해 queue 역할을 list가 대신한다!
list.pop(0) # deque와 차이점을 가지는 부분. 시간 복잡도가 O(n)이다!

 

 

 

 

---

 

 

하지만, list의 pop() 함수는 시간 복잡도가 O(n)으로 좋지 않다고 한다!!

 

그래서 사용하는 것이 collections 라이브러리의 deque는 O(1)로,

보다 시간 복잡도를 줄일 수 있다!!

 

참고 : https://wiki.python.org/moin/TimeComplexity

TimeComplexity - Python Wiki

 

---

 

 

 

 

 

 

✌ 그래서 나온 것이 deque 사용하기!!

 

from collections import deque

queue = deque() #deque(1) 이런 식으로도 가능하다!
queue.append(1)
queue.popleft()

 

 

 

 

---

 

 

그래서 deque를 기준으로 BFS 알고리즘을 구현해보자!!

 

 

 

👊 graph는 다음과 같은 형태로 구성된다!!

graph = [[1,2,4], [0,2], [0,1,3,4], [2,4], [0,2,3]]

 

0부터 4까지 노드가 주어졌을 때, 각자 인접한 노드를 적어둔 것이다!

그러니, 인덱스를 노드를 나타낸다고 생각했을 때 위와 같은 형태가 나오게 된다!!

 

 

만약, 노드가 0부터 시작되는 정수의 형태가 아니라면, 이런 식으로 적으면 되지 않을까? 생각한다

(테스트 해보고 아니라면,, 수정할게요😅😅😅)

grpah = ['A' : ['B','C', 'D'], 'B' : ['A', 'C'], 'C' : ['A', 'B', 'D', 'E'], 'D' : ['C', 'E'], 'E' : ['A', 'C', 'D']]

 

 

 

🤛 BFS 는 다음과 같은 형태가 된다!!

 

visited = [False] * 5 # 이런 식으로 선언을 하면 인덱스를 지정하여 접근이 가능하다!!

def bfs(start):
    queue = deque([start]) # 선언과 동시에 start를 넣어둘 수 있다!
    visited[start] = True
    
    while queue: # queue가 비게 될 때까지 반복한다.
        v = queue.popleft()
        
        for x in graph[v]:
            if not visited[x]:
                queue.append(x)
                visited[x] = True
                
bfs(0)

 

 

해당 알고리즘을 이해 못 하겠거나 BFS를 이해 못 하겠다면 코드를 실행해보는 게 직빵이다!!

 

print()문을 넣고 실행을 해보면, BFS가 잘 구현되었다는 것을 알 수 있다!!

 

 

 

 

 

 

 

 

 

 

 

 

 

 

---

 

 

 

 

 

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

 

 

• stack 개념을 사용한다!!
• Recursive 함수가 제일 많다!! -> 재귀함수만 생각하면 뚝딱 해결!!

 

 

 

 

BFS에 비해 너무 적다고 느끼는 것은..

기분 탓이 아니다..

 

스터디를 같이 하는 다른 친구가 DFS 설명을 맡았고, 내가 BFS 설명을 맡아..

아주 쬐끔 더 BFS를 자세히.. 이해한 것뿐이다...ㅎ

 

아무튼 DFS는 사실 코드도 좀 간단하다.

바로 넘어가도 될 정도..

BFS를 깔끔하게 이해했다면, DFS는 금방 이해가 된다!!

 

 

 

 

 

그래서 냅다 코드를 던져보자면, 

 

visited = [False] * (노드 개수)
def dfs(start):
	visited[start] = True
    
    for x in graph(start):
    	if visited[start] == False :
        	dfs(start)
dfs(0)

 

 

쏘 이지..

 

BFS를 이해했기 때문에 쉬워지는 DFS이다!

DFS는 깊이 탐색이기 때문에 하나를 계속 파는 것이 중요하다!!

그렇기 때문에 재귀 함수를 통해 들어가고 들어가고 또 들어가는 것!!

 

 

 

 

 

 

 

 

 

 

 

---

이렇게 해서 얼렁뚱땅 오늘도 스터디 끝!!

사실 이전 스터디에 다룬 코드들도 정리해야 하는데, 너무 귀찮다..

 

할 게 많은데 할게 밀렸는데 너무 많다..

 

 

아무튼 오늘도 이렇게 끝!!

다음부터는 DFS/BFS 해결할 수 있기를 바라며!!

 

다음에는 미로찾기 알고리즘과 달팽이 배열을 알아보고자 한다!! (장담 못함)

 

 

 

 

그럼 안녕🙌🙌🙌🙌🙌🙌🙌🙌🙌🙌🙌🙌🙌