[알고리즘/Python] DFS(깊이 우선 탐색)과 BFS(너비 우선 탐색) 구현

DFS (Depth-First-Search)

그래프에서 가장 깊은 부분을 우선으로 탐색하는 알고리즘이다.

 

진행 가능한 노드가 없을 때까지 깊게 파고드는 방식이며, 

더이상 방문 가능한 노드가 없다면 이전의 위치로 돌아와 다른 방향으로 깊게 파고든다.

 

주로 모든 노드를 방문하고자 하거나,

이동할때 마다 가중치가 붙어서 이동하는 경우,

그리고 이동 과정에서 여러 제약이 있는 경우에 이 방식을 사용한다.

또한 검색 대상 그래프가 정말 크다면 DFS를 사용한다.

 

DFS 알고리즘을 구현할때는 재귀로 구현할 수도 있고, 스택을 이용해서 구현할 수도 있다.

코딩테스트에서 구현할때는 재귀로 구현하는것이 더 선호되는 편이다.

 

 

 

   장점 

1.  BFS에 비해 저장공간의 필요성이 적다(적은 메모리 사용). 백트랙킹을 해야하는 노드들만 저장해주면 된다.
2.  찾아야 하는 노드가 깊은 단계에 있는 경우 BFS보다 빠르다.
   

   단점

1.  DFS를 통해서 얻어진 해가 최단 경로라는 보장이 없다. DFS는 해에 도착하면 탐색을 종료하기 때문이다 ( ==> 최단경로 문제에서는 BFS 사용하기!)
2.  해가 없는 경로를 탐색 할 경우 단계가 끝날 때까지 탐색한다.

 

 

여기서 잠깐

그래프 순회를 할때 특정 노드가 방문되었는지 안되었는지 확인하기 위한 방법으로는 2가지가 있다.

 

1.  텅 빈 리스트를 만들고 특정 노드를 방문하면 리스트에 append 한다.
2.  크기가 노드 개수만큼인 리스트를 만들고 False로 채운다. 특정 노드를 방문하면 해당 위치를 True로 교체 

 

  **재귀로 DFS 구현(append 방식)

def DFS_Recursive(graph,v,visited):
  visited.append(v)
  for w in graph[v]:
    if w not in visited:
      DFS_Recursive(graph,w,visited)

#각 노드가 연결된 정보를 표현 
graph={
  1:[2,3,4],
  2:[1,4,5],
  3:[1],
  4:[1,2,5],
  5:[2,4]
}
visited=[]
DFS_Recursive(graph,1,visited)
print(visited)

위에 코드랑 아래 코드는 함수의 return값에서 차이가 있는 코드이다.

구글링을 아무리 해봐도 어떤 코드가 더 빠르고 깔끔한 코드인지 잘 모르겠다ㅠ,,

def DFS_Recursive(graph,v,visited):
  visited.append(v)
  for w in graph[v]:
    if w not in visited:
      visited=DFS_Recursive(graph,w,visited)
  return visited

#각 노드가 연결된 정보를 표현 
graph={
  1:[2,3,4],
  2:[1,4,5],
  3:[1],
  4:[1,2,5],
  5:[2,4]
}
visited=[]
visited=DFS_Recursive(graph,1,visited)
print(visited)

 

 

**재귀로 DFS 구현(True,False 방식)

def DFS_Recursive(graph,v,visited):
  visited[v]=True
  print(v)
  for w in graph[v]:
    if not visited[w]:
      DFS_Recursive(graph,w,visited)

#각 노드가 연결된 정보를 표현 
graph={
  1:[2,3,4],
  2:[1,4,5],
  3:[1],
  4:[1,2,5],
  5:[2,4]
}
visited=[False]*(5+1)
#index처리를 깔끔하게 하기 위해 1칸 더 크게 만듬
DFS_Recursive(graph,1,visited)

난 첫번째 방식이 더 맘에 들긴 한다.

하지만 특정 노드가 방문되었는지 확인하는 과정에서

두번째 방법은 바로 index값으로 접근을 하기 때문에 O(1)의 시간만에 확인이 가능하지만

첫번째 방법은 visited리스트를 모두 다 뒤져봐야 하기 때문에 더 긴 시간이 소요된다.

 

 

 

 

**스택으로 DFS 구현

graph={i:[] for i in range(1,v+1)}
#v는 전체 노드의 개수

def DFS_Stack(graph,v):
  visited=[]
  stack=[v]
  while stack:
    v=stack.pop()
    if v not in visited:
      visited.append(v)
      for w in graph[v]:
        stack.append(w)
  return visited
#각 노드가 연결된 정보를 표현 
graph={
  1:[2,3,4],
  2:[1,4,5],
  3:[1],
  4:[1,2,5],
  5:[2,4]
}
result=DFS_Stack(graph,1)
print(result)

 

 

추가적으로 코딩테스트에서는 그래프의 값(?)이 기본적으로 주어지지 않고

직접 edge가 연결하는 두 노드(vertex)의 번호를 통해서 개별적으로 연결해야 한다.

이때 그래프를 만드는 코드는 아래와 같다.

graph={i:[] for i in range(1,v)}
#v는 노드의 개수

 

 

 

---

 

BFS (Breadth-First-Search)

그래프에서 특정 노드에서 시작해서 그와 인접한 노드들을 우선적으로 탐색하는 방법이다.

 

시작 노드에서부터 가까운 노드를 먼저 방문하고,
더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서

멀리 떨어져 있는 노드를 나중에 방문함으로써 그래프를 wide하게 탐색한다.

 

주로 미로찾기 등 두 노드 사이의 최단경로 

혹은 임의의 경로를 찾고자 할때 이 방법을 사용한다.

또 검색대상의 규모가 크지 않고, 검색 시작 지점으로부터 찾고자 하는 대상이 별로 멀지 않을때 사용한다.

 

BFS 알고리즘을 구현할때는 큐를 이용해서 구현한다.

 

 

 

   장점 

1.  단순 검색 속도가 DFS(깊이 우선 탐색)보다 빠르다.
2.  너비를 우선 탐색하기 때문에 답이 되는 경로가 여러개인 경우에도 최단경로임을 보장한다.  (모든 edge들의 가중치가 같다는 가정 하에)
3.  노드의 수가 적고 깊이가 얕은 경우 빠르게 동작할 수 있다

    단점

1.   재귀호출의 DFS와는 달리 큐에다가 다음에 탐색할 정점들을 모두 다 저장해야 하므로 저장공간이 많이 필요하다.
2.   노드의 수가 많아지면 탐색해야 하는 노드또한 많아지므로 비현실적이다.

 

 

def BFS(graph,v):
  queue=deque([v])
  visited=[v]
  while queue:
    v=queue.popleft()
    for w in graph[v]:
      if w not in visited:
        queue.append(w)
        visited.append(w)
  return visited