[We-Co] DFS, BFS - Python

안녕하세요. 위기의 코딩맨입니다.

코딩테스트를 진행하기 위해서는 알아야할 DFS, BFS!

깊이우선탐색, 너비우선탐색 방법에 대해서 알아보도록 하겠습니다.

dict_ = {'A' : {'B', 'C'},
         'B' : {"A", "D"},
         "C" : {"A", "D", "E"},
         "D" : {"B", "C", "F"},
         "E" : {"C", "G", "H"},
         "F" : {"D"},
         "G" : {"E", "H"},
         "H" : {"E", "G"}}

 

[ DFS - 깊이 우선 탐색 ]

DFS는 Depth First Search로 스택을 이용한 미로를 탐색하는 알고리즘과 유사합니다.

한 방향으로 진행하다 더 이상 갈 수 없게 되면 다시 가장 가까운 곳으로 이동하여 다른 방향을 탐색하는 방식입니다.

 

위에 선언한 python의 dict를 사용하여 구조를 만들어 봤습니다.

해당 dict를 이용하여 DFS를 알아보도록 하겠습니다.

하지만 print해서 선언한 dict를 보면 따로 랜덤하게 들어가더라구요

print(dict_)

변경된 DIct

왜 이런지... 방법을 모르겠지만 문제는 없습니다.!

 

def DFS(graph, start, visited):   

  if start not in visited:    

    visited.add(start) 

    print(start,end='')  

    nbr = graph[start] - visited 

    for v in nbr: 

      DFS(graph, v, visited)   

print("DFS : ", end ='')

DFS(dict_,"A",set())

 

결과

DFS의 인자를 dict_, 시작점, 방문한 목록 받게됩니다.

Start가 visited에 들어 있지 않으면 해당 값을 방문 인자로 등록하고,

인자를 출력 시키고 목록에서 지우고 방식을 반복하게 됩니다.

 

[ BFS - 너비 우선 탐색 ]

BFS는 Breadth First Search로 시작 정점부터 가까운 정점을 먼저 방문하고, 

멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법을 의미합니다.

가까운 거리에 있는 정점을 차례로 저장하고, 들어간 순서대로 꺼낼 수 있는 큐(Queue)를 사용합니다.

 

정점을 방문할 때마다 방문처리, 큐에 인접 정점을 삽입하고, 

맨 앞의 정점을 꺼내서 그 정점과, 인접한 정점들을 차례로 방문처리합니다.

해당 방식을 Que가 공백이 될때까지 반복처리 합니다.

 

import queue

def BFS(graph, start):

  print("BFS : ", end='')

  # 방문처리

  visited = {start}

  # 큐 생성

  que = queue.Queue()

  que.put(start) 

  while not que.empty():

    #정점 v, 방문 출력

    v = que.get()

    print(v,end='')

    # nbr = v인접 정점 - 방문 정점

    nbr = graph[v] - visited 

    # nbr의 인접 정점 방문처리, 큐 삽입

    for u in nbr:

      visited.add(u)

      que.put(u)

 

import로 queue를 선언하고

BFS에 dict_인자와 "A"의 시작점을 보냅니다.

 

BFS(dict_,"A")

결과로는 

결과

 

 

 

앞으로 DFS, BFS를 응용하여 코딩테스트 하는 방식도 알아보도록 하겠습니다.