DFS와 BFS

프로그래밍에서 그래프는 크게 2가지 방식으로 표현할 수 있는데
코딩 테스트에서는 이 두 방식 모두 필요하니 두 개념에 대해 바르게 알고 있어야 한다.

인접 행렬

방향 그래프

그래프의 연결 관계를 이차원배열로 표현한다.

보통 adj[][]형태로 많이 작성한다.

// adj[i][j]: i에서 j로 가는 간선이 있다면 1, 없다면 0

인접 행렬 왜 사용?

1. [장점]

   • 구현이 빠르다
   • 노드가 서로 연결되어있는지 확인하기 쉽다.

   // adj[i][j] = 1이면 노드 i와 노드 j는 연결되어 있다.
   ⇒ 시간복잡도 O(1)

2. [단점]

   • 전체 노드 개수: V 간선의 개수: E
   • 특정 노드에 연결된 모든 노드를 검색할 때, adj[i][1] ~ adj[i][V]를 전부 확인해야한다.
     시간복잡도 O(V)

   ⇒ 전체 노드 탐색 시 시간복잡도 O(V*V)

예제 with python

inf = 99999999999

graph =[
	[0,7,5],
	[7,0,INF],
	[5,INF,0],
]

print(graph)

인접 리스트

인접 리스트 왜 사용?

1. [장점]

   • 실제 연결된 노드만 저장한다

   • 모든 vector의 원소의 개수 합 = 간선의 개수

     ⇒ 전체 노드 탐색 시 시간복잡도 O(E)2

2. [단점]

   • 노드가 서로 연결되어있는지 확인하는데 오래 걸린다.
   • 인접 행렬은 adj[i][j]의 값이 1인지 확인하면 연결된 것을 알지만 인접 리스트의 경우는 adj[i]가 j를 원소로 갖는지 확인해봐야한다.
     ⇒ 시간복잡도 O(V)

예제 with python

graph = [[] for _ in range(3)]

#노드 0에 연결된 노드 정보 저장(노드,거리)
graph[0].append((1,7))
graph[0].append((2,5))

graph[1].append((0,7))

graph[2].append((0,5))

print(graph)

이것이 취업을 위한 코딩 테스트다 with 파이썬

DFS

• 시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색
• 더 이상 갈 곳이 없게 되면, 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아옴
• 다른 방향의 정점으로 탐색을 계속 반복하여 결국 모든 정점을 방문하여 순회
• 가장 마지막에 만났던 갈림길의 정점으로 되돌아가서 다시 깊이 우선 탐색을 반복해야 하므로 후입선출 구조의 스택을 사용

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

visited = [False] * 9

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

dfs(graph, 1, visited)

BFS

from collections import deque

def bfs(graph,start,visited):

  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]
]

visited= [False] * 9

bfs(graph,1, visited)