탐색 알고리즘 DFS / BFS - 파이썬(Python)

필요 사전 개념

탐색 알고리즘에 들어가기 앞서 노드에 대해 잘 모른다면 이전 발행 글 노드를 표현하는 법을 보고 가자

그래프 노드로 표현하기 - 파이썬(Python)

 

그래프 탐색

• Edge를 따라서 모든 Node를 방문하는 것을 그래프 탐색이라고 함 → 대표적인 방법으로 DFS, BFS가 있음

 

DFS : Depth Fist Search (깊이우선탐색)

기본 원리 및 동작

• 깊은 부분을 우선적으로 탐색
• Stack을 활용하여 구현
• Stack의 특성인 FILO(First In Last Out) 방식 (데이터를 집어넣는 순서와 꺼내는 순서가 역방향)

 

 

1. 탐색 시작 노드를 스택에 삽입을 하고 방문처리를 함.
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면, 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 2번의 과정을 더 이상 수행할 수 없을 때 까지 반복한다.

(참고) 방문 처리: 스택에 한 번 삽입되어 처리된 노드가 다시 삽입되지 않게 체크하는 것을 의미한다. 방문 처리를 함으로써 각노드를 한 번씩 처리를 할 수 있음.

 

 

파이썬의 리스트를 활용한 Stack의 구조 구현

• 기본적인 내용을 구현하기 위해서는 
  (입력) 그래프의 정보, 시작 노드 → (출력) 탐색한 노드들의 순서
  1. 기본적으로 지금 어느 노드에 가봐야 하는지 하는 것과 내가 이미 방문을 했는지에 대한 것을 처리하는 2개의 대상이 필요함
  2. 시작점을 통해서 일단 그 시작점에 연결된 것들을 다 탐색을 해본다.
  3. 탐색을 하는 과정에서 이미 방문을 하였는지, 안 하였는지에 따라서 → 이미 방문을 했다면 안 하고 새로운 곳이면 방문을 해야하는 곳으로 가서 할 것
• 참고) 이 경우에 좀 더 쉽게 처리를 하기 위해서 파이썬의 Dict로 인접리스트를 구현을 함.
  • Why? 파이썬의 dict는 Hash Table의 역할을 하고 있으며, 노드의 중복 여부에 대해서 key로 처리를 하고 있으며, 탐색에 대한 시간도 O(1)의 복잡도를 가지고 있어서임

# 위의 주어진 예제에 대해서 그래프의 연결리스트를 아래와 같이 dict로 구현
# 탐색에 대한 지도를 코드화
#     ==> 인접 리스트 : 리스트로 표현할 때
#         가상의 0번 도시가 있다고 가정하고 표현
graph_list = [
    [], # <-- 가상의 0번 도시는 연결되어 있지 않다 :인덱스처리용 더미
    [2,3,8], # <- 1번 도시와 연결된 도시들
    [1,7],   # <- 2번 도시와 연결된 도시들
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

앞에서는 지나간 노드들에 대해서 보면 1 → 2 → 7 → 6 → 8 → 3 → 4 →5였는데, 지금 위에서 한 대로 하면 순서가 좀 다르게 1→ 8 → 7 → 6 → 2 → 3 → 5 → 4로 순서가 조금 다름
이유는 리스트에서 병합을 하면서 pop으로 꺼내면서 맨 뒤의 제일 큰 숫자의 값이 제일 먼저 나오게 되어서 다 노드들을 돌지만, 위에서 한 그림과 그 순서가 다르게 됨
아래의 경우는 각 노드에서 그 다음 노드를 갈 때, 큰 값이 아니라 제일 작은 값으로 기준을 해서 하기 위해서는 graph[node]에서 [2,8]에 대한 값을 [8,2]로 순서를 뒤집어서 해주면 된다.

 

DFS 코드 구현

• 입력 : 지도, 시작점
  • 필요한 세팅 변수 : 방문할 곳 리스트(To Do List)
  • 필요한 세팅 변수 : 방문한 곳 리스트(Done List)
• 방문할 곳 리스트가 빌 때 까지 while을 활용
  • while 리스트 : 빈 리스트가 될 때 까지
    • 일단 방문할 곳 1개 꺼내 : Stack => pop() 이동
• 2가지를 체크
  1. 여기가 내가 처음 온 곳이면?
     • 방문한 곳 리스트 추가 append(뒤로)
  2. 여기에서 연결된 곳이 어딘가?
     • 방문할 곳 리스트에 추가 append(뒤로)

# 입력 : 지도, 시작점
# 기능 : DFS방식으로 주어진 지도를 탐색/방문
# 출력 : 방문한 기록을 제출

def dfs_m1( graph, start):
    # 초기 변수들에 대한 세팅
    need_visit = list()	# 방문할 곳 리스트 (To Do List)
    visited    = list()	# 방문한 곳 리스트 (Done List)
    need_visit.append( start )	# 처음 출발점을 방문할 곳에 추가

    # 출발
    while need_visit:	# need_visit 할 목록이 없을 때 까지
    	# 1) 방문할 곳을 맨 뒤에서 꺼냄 (Stack)
        node = need_visit.pop()
        # 2) node 내가 이미 갔던 곳인지 체크
        #    ==> 갔던 곳이면 pass
        #    ==> 신규 방문 : (Done List) 리스트에 추가
        #                    + 이 곳에서 연결된 곳들을 받아서
        #                      (To Do List) 리스트에 추가를 해야함
        if node not in visited: # <- 신규 방문지
            # 2-1) (Done List) 리스트에 추가
            visited.append(node)
            # 2-2) 연결된 도시 (To Do List) 리스트에 추가
            need_visit.extend(graph[node] )
    return visited
    
dfs_m1( graph_list, 1)	# 위에서 설정한 graph_list를 지금 만든 함수에 넣어보자

[1, 8, 7, 6, 2, 3, 5, 4]

 

• 작은 숫자 도시부터 방문하고 싶다면

# 방문 순서를 같은 연결이면 작은 숫자 도시부터
# reversed() 사용
def dfs_m2( graph, start):
    need_visit = list()
    visited    = list()
    need_visit.append( start )
    while need_visit:
        node = need_visit.pop()
        if node not in visited: # <- 신규 방문지
            visited.append(node)
            # --> 순서를 지정 : 지도 구성의 역순으로 돌리면,
            #       역방향 : .reverse(), reversed(), [::-1]
            temp = graph[node]
            temp_reverse = list(reversed(temp))
            need_visit.extend( temp_reverse )
    return visited
    
dfs_m2( graph_list, 1)

[1, 2, 7, 6, 8, 3, 4, 5]

 

 

BFS는 아래 글에서 알아보자

탐색 알고리즘 DFS / BFS - BFS