[알고리즘] 4. DFS, BFS, 백트래킹

1. 그래프 Graph

예시

• 지도, 내비게이션
• SNS, 메신져 → 계정 간 관계도
• VCS (Version Control System)

개념

• Vertex(=node): 정점, Edge: 간선
• 무방향 그래프(=양방향 그래프): 방향이 없다, 방향 그래프: 방향이 있다
• 순환그래프(Cyclic), 비순환그래프(Acyclic) → 사이클이 되는 부분이 있나 없나로 판단
• DAG(Directed Acyclic Graph): 방향성 비순환 그래프 ex) VCS
• 연결요소(Connected Component): 연결이 된 그래프 덩어리

코드방식

1. 인접행렬: 행→열 방향으로 가는 간선이 있는 지 없는 지 행렬로 나타낸다.
   ※ 무방향(=양방향)은 대칭이 된다.
2. 인접리스트(=연결리스트): 시작노드→도착노드들로 하여 연결리스트로 나타낸다.
   ※ 파이썬에서는 그냥 리스트로 구현한다...
3. □ 인접행렬 vs △ 인접리스트 비교
   △ 메모리 측면: 간선이 적을 수록 인접리스트가 유리 (간선이 많을 경우 인접행렬과 별 차이가 없음)
   □ 시간 측면: 간선 정보에 접근시 인접행렬이 유리

2. 트리

개념

<수학적 개념>

• 순환성이 없는 무방향 그래프
• 특정하지 않는 한 어떤 노드든지 루트(root)가 될 수 있다.

<자료구조적 개념>

• 부모, 자식 관계가 있는 방향 그래프: 자료구조적인 개념
• 루트(root)는 하나다.

<공통 개념>

• 가장 바깥쪽 노드는 리프노드(leaf node)
• node A에서 node B로 가는 경로는 반드시 존재하며 유일하다.
• 노드 개수 = 간선 개수 + 1

3. DFS 깊이 우선 탐색 (Depth First Search)

개념

• 트리에서 깊이가 갈 수 있는 대로 먼저 탐색하는 것
• 스택이나 재귀를 사용해서 구현한다.

코드예시

adj = [[0] * 13 for _ in range(13)]

adj[0][1] = adj[0][7] = 1
...

# 현재 방문한 노드를 파라미터로 받는다
def dfs(now):
	# 다음 방문할 연결된 노드를 탐색
	for nxt in range(13):
    	if adj[now][nxt]:
        	dfs(nxt)

dfs(0)

4. BFS 너비 우선 탐색 (Breadth First Search)

개념

• 트리에서 좌우(=너비)로 갈 수 있는 대로 먼저 탐색하는 것
• 큐를 사용해서 구현한다.
• root부터 넣고, pop을 하면서 갈 수 있는 노드를 큐에 넣는다. (pop하고 넣고의 반복)

코드예시

from collections import deque
adj = [[0] * 13 for _ in range(13)]

adj[0][1] = adj[0][2] = 1
adj[1][3] = adj[1][4] = 1
...

def bfs():
	dq = deque()
    dq.append(0)
    while dq:
    	now = dq.popleft()
        for nxt in range(13):
        	if adj[now][nxt]:
            	dq.append(nxt)

bfs()

※ DFS & BFS

• 공통점

  • 둘다 그래프 탐색 알고리즘이다.
  • 완전탐색 알고리즘이다.

• 차이점

  • DFS: 현 경로상의 노드들만 기억하면 되므로 저장공간 수요가 비교적 적다.
  • DFS: 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.
  • BFS: 특정 노드 탐색시 최단 거리를 보장할 수 있다.
  • BFS: 노드 수가 적고 깊이가 얕은 해가 존재할 때 유리하다.

• 시간복잡도

  • 인접행렬: O(V^2)
  • 인접리스트: O(V+E) or O(max(V, E)): V, E 한쪽이 무지 클 경우 다른 한쪽은 무시된다.

예제

• 길찾기 문제
  • 보통 위, 아래, 좌, 우 4방향이 많다.
  • 방향값을 미리 코드에 짜두고 for문으로 순회하는 기법를 익힌다.
  • 범위 체크, 방문 체크를 해야한다.

# 시계방향
dy = (0, 1, 0, -1)
dx = (1, 0, -1, 0)
N = int(input())
chk = [[False * N for _ in range(N)]]

def is_valid_coord(y, x):
	return 0 <= y < N and 0 <= x < N

# dfs 방식
def dfs(start_y, start_x):
	chk[y][x] = True
    for k in range(4):
        ny = y + dy[k]
        nx = x + dx[k]
    	if is_valid_coord(ny, nx) and not chk[ny][nx]:
            dfs(ny, nx)

# bfs 방식
def bfs(start_y, start_x):
	q = deque()
    q.append((start_y, start_x))
    while len(q) > 0:
    	y, x = q.popleft()
        chk[y][x] = True
    	for k in range(4):
        	ny = y + dy[k]
            nx = x + dx[k]
    		if is_valid_coord(ny, nx) and not chk[ny][nx]:
            	q.append((ny, nx))

5. 백트래킹

개념

• 기본적으로 모든 경우를 탐색, DFS/BFS와 방식이 유사
• "가지치기를 통해 탐색 경우의 수를 줄인다" 차이가 있다.
  • 최악의 경우, 모든 경우를 다 살펴볼수도 있지만 가능한 덜 보겠다는 전략
  • 가망성이 없으면 가지 않는다!