[python] DFS / BFS

탐색 알고리즘을 알기 전에 기본적인 사전 지식들이 조금 필요하다.

 

1. 스택 : 선입후출(FILO)

2. 큐 : 선입선출 (FIFO)

3. 그래프 개념

 

그래프는 표현하는 방식에 인접 행렬과 인접 리스트가 있는데, 나는 인접리스트를 이용할 것이다.

 

1. DFS (Depth - First Search)

:  그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘

 

 

기본적인 동작 방식 

 

1.  탐색 시작노드를 스택에 삽입하고 방문 처리를 한다.
2.  스택의 최상단 노드에 방문하지 않는 인접노드가 있으면 그 인접 노드를 스택에 넣고 방문처리를 한다.
3.  방분하지 않은 인접노드가 없으면 스택에서 최상단 노드를 꺼낸다
4.  2,3번을 반복한다.

 

빨간색 숫자 순서대로 보면 된다.^^..

 

재귀 함수를 이용해 코드로 표현해보자

def DFS(garph,v,visited):
    
    visited[v] = True #방문처리
    print(v,end=" ")

    #현재 노드와 연결된 다른 노드를 방문
    for i in graph[v]:
        if not visited[i]:
            DFS(graph,i,visited)

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

#방문 저장 list
visited = [False]*9

DFS(graph,1,visited) #1번 노드부터 탐색

#출력 결과 : 1 2 7 6 8 3 4 5

 

 

2. BFS (Breadth First Search)

 

: 너비 우선 탐색, 가까운 노드 부터  탐색하는 알고리즘.

  깊이 우선 탐색은 최대한 멀리 있는 노드 부터 검색했다면 BFS는 그 반대라고 생각하면 된다. 

  또 스택을 사용하는 DFS와 달리 큐를 사용한다

 

기본적인 동작방식

 

1. 탐색 시작 노드를 큐에 삽입 하고 방문처리
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리
3. 2번 반복

 

 

bfs도 코드로 구현해보자

def BFS(graph,start,visted):

    queue = deque([start])
    visited[start] = True

    while queue:

        v= queue.popleft()
        print(v,end=" ")

        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True
                
graph=[
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

#방문 저장 list
visited = [False]*9

BFS(graph,1,visited)
# 1 2 3 8 7 4 5 6

 

2차원 배열 문제를 풀때 그래프 형태로 생각하면 훨씬 수월하게 풀 수 있다 ! 

자주 연습하자