DFS (깊이 우선 탐색) , BFS (너비 우선 탐색)

탐색 알고리즘 (DFS)

DFS의 정의

• Depth-First Search : 깊이 우선 알고리즘, 그래프의 깊은 노드를 우선적으로 탐색하는 알고리즘이다.
• 때문에 DFS를 이해하려면 그래프와 그래프 탐색에 관한 부분을 알아야한다. + 스택(stack)
• 흔히 미로 탐색으로 비유한다. 막다른 길에 도달할때 까지 한쪽방향을 탐색하다가, 끝을 보면 다시 갈림길로 돌아와서 다른 길을 탐색하는 방법이다.
• 완전탐색의 일종이다.

DFS의 장점

현재 탐색중인 노드들만 기억하기 때문에 메모리 사용이 적고, 당연한 이야기지만 찾으려는 노드가 깊을 경우에 BFS보다 빠르게 찾을 수 있다.

DFS 단점

해가 없는 경로를 탐색하는 경우에도 경로가 끝날때 까지 탐색한다. (이를 방지하기 위해 조건을 지정하고 원래 위치로 되돌아오는 Backtracking을 사용할 수 있다.)

그래프

그래프는 위 그림처럼 노드(동그라미)와 간선(선) 으로 표현된다. 그래프의 탐색이라고 하면 하나의 노드를 시작으로 다수의노드를 방문하는 과정을 말한다. 간선으로 직접 연결된 두 노드는 인접하다(adjacent)라고 한다.

그래프를 프로그래밍 언어로 표현

크게 2가지 방식으로 표현 가능하다.

• 인접 행렬 : 2차원 배열로 그래프의 연결관계를 표현하는 방법 (Adjacency Matrix) 행렬을 나타내기 위해 2차원 배열을 사용한다.
• 인접 리스트 : 리스트로 그래프 연결 관계를 표현하는 방법 (Adjacency List) 2차원 리스트를 사용해야 하지만, 노드와 거리를 담기 위한것이므로 인접행렬과는 다르게 이해해야한다.

인접행렬 방식

그래프의 노드가 1부터 6까지이므로 총 6개이다. 그래서 각 6행 6열이 되고, 행렬에서 각 요소값의 1은 연결되었다는 의미이고, 0은 연결되지 않았다는 의미가 된다.

인접 리스트 방식

인접리스트 방식은 모든 노드에 해당 노드와 연결된 정보를 저장한다.

예를들어서 위 그림에서 노드 1을 보게되면, 5와 2가 연결되어있다. 그럼 1번 노드 자리에 해당하는 정보를 넣어주면 된다. ad_list[1].append(2,5)

 

 

인접행렬 vs 인접리스트

뭘 사용하는게 좋을지 비교.

인접리스트는 필요한만큼만 (정점과 간선의 개수만큼만) 메모리를 소모하게되지만 , 인접행렬은 무조건적으로 정점x정점 만큼의 공간을 할당해야한다.

• 인접행렬 : O(V^2)
• 인접리스트 : O(max(V+E))

탐색 속도같은경우는 인접행렬이 더 빠르다. 예를들어서 1과 3의 관계가 알고싶다면 array[1][3]으로 접근하게되면 O(1)이다. 하지만 인접리스트에서 확인하려면 1이나 3과 연결된 노드들을 전부 확인해야한다. 따라서 최악의경우에는 O(N)이된다.

간단하게 한줄로 정리하면, Node가 많다면 인접리스트를, Edge가 많다면 인접행렬을 쓰는게 좋다.

일반적인 코딩테스트나, PS에서는 시간초과가 메모리초과보다 잦기때문에 인접행렬을 쓰는경우가 더 많다고한다.

 

DFS의 동작 방식

방문 처리 : 스택에 삽입되었던 노드가 중복적으로 또 다시 삽입되지 않도록 하기 위함.

1. 탐색을 시작할 첫번째 노드를 스택에 삽입한다. (방문처리도 한다)
2. 스택에 삽입된 최상단 노드 주변에 방문하지 않았던 인접 노드가 있으면, 해당 노드를 스택에 삽입하고 방문처리한다.
3. (이때 인접 노드가 1개보다 많다면 더 작은 노드부터 처리한다.)
4. 2번을 실행할수 없으면(최상단 노드에 방문하지 않은 인접 노드가 없으면) , 스택에서 최상단 노드를 꺼낸다.
5. 2 - 3번 과정을 반복한다. (모든 노드가 방문처리 될때까지)

이렇게 모든 노드를 탐색하게 되면 시간 복잡도는 O(N)이 된다.

재귀함수의 수행은 스택 자료구조를 이용한다.

간단하게 재귀함수의 동작원리를 보면....

• 재귀의 내부 수행을 보면, 가장 마지막에 호출되었던 함수의 수행이 끝나야, 그 앞의 함수의 호출이 종료된다.

def recursive_function(i):
	if i == 5:
		return
	print("%d 번째 재귀함수가 실행되었습니다."%i)
	recursive_function(i+1)
	print("%d 번째 재귀함수가 종료되었습니다."%i)

recursive_function(1)

>>> 출력 내용
1 번째 재귀함수가 실행되었습니다.
2 번째 재귀함수가 실행되었습니다.
3 번째 재귀함수가 실행되었습니다.
4 번째 재귀함수가 실행되었습니다.
4 번째 재귀함수가 종료되었습니다.
3 번째 재귀함수가 종료되었습니다.
2 번째 재귀함수가 종료되었습니다.
1 번째 재귀함수가 종료되었습니다.

 

graph

graph = [
  [],
  [2, 3, 8],
  [1, 7],
  [1, 4, 5],
  [3, 5],
  [3, 4],
  [7],
  [2, 6, 8],
  [1, 7]
]
visited = [False for i in range(len(graph))]

재귀로 구현한 dfs

def dfs(graph, node, visited) :
  visited[node] = True
    for i in graph[node]:
    if not visited[i] :
      dfs(graph, i , visited)

탐색 알고리즘 (BFS)

BFS의 정의

Breadth-Frist-Search : 너비 우선 알고리즘, 가까운 노드부터 탐색하는 알고리즘이다.

DFS와는 다르게 큐 자료구조를 사용한다. 인접한 노드를 반복적으로 큐에 넣고, 먼저 들어온 노드가 먼저 나가게되어 가까운 노드부터 탐색하게 되는 구조이다.

BFS 구현

1. 탐색 시작 노드를 큐에 삽입하고 방문처리한다.
2. 큐에서 노드를 꺼내고, 꺼낸 노드 주변에서 방문하지 않은 노드를 "모두" 큐에 삽입한다. 그리고 삽입된 큐는 방문처리한다. (작은 숫자의 노드부터 삽입)
3. 2번을 반복한다.

DFS와 마찬가지로 시간복잡도는 O(N)이다.

from collections import deque 

def bfs(graph, start, visited):
  queue = deque([start])
  visited[start] = True
  while queue:
    node = queue.popleft()

    for i i n graph[node]:
      if not visited[i]:
        queue.append(i)
        visited[i] = True

 

 

 

* BFS / DFS 관련 문제

 

 

https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

#가장 기본적인 BFS문제
from collections import deque


n , m = map(int, input().split())
grid = []
dx = [0,0,1,-1]
dy = [1,-1,0,0]
for _ in range(n):
    grid.append(list(input()))

def bfs(x,y):
    q = deque()
    q.append((x,y))
    grid[0][0] = 1
    while(q):
        x,y = q.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or ny < 0 or nx >= n or ny >= m :
                continue
            if grid[nx][ny] == "1":
                q.append((nx,ny))
                grid[nx][ny] = grid[x][y] + 1

    return grid[n-1][m-1]


print(bfs(0,0))

 

 

 

https://infinitt.tistory.com/347

백준 (boj) 파이썬 - 1260 : DFS와 BFS

순수하게 DFS와 BFS를 구현하는 문제이다. 개념을 공부하고 처음으로 풀면 좋을것 같다.