알고리즘 문제 유형 - 그래프 (DFS, BFS, 백트래킹, 제약충족문제)

🔷 그래프

🔹구성

정점(node), 간선(edge)

 

🔹그래프 종류

• 방향 기준
  • 무방향(= 양방향) 그래프
  • 방향 그래프
• 순환성 기준 
  • 순환 그래프 (cyclic graph) - 한군데라도 cycle이 있으면 순환그래프
  • 비순환 그래프(acyclic graph) - cycle이 하나도 없으면 비순환 그래프

방향성 비순환 그래프(DAG, Directed Acyclic Graph )

연결 요소로 이루어진 그래프도 존재

 

 

🔷 그래프 표현 방법

1. 인접행렬 (Adjacency Matrix)

간선 정보를 0 또는 1로 해서 [출발노드][도착노드]로

가는 간선이 존재하면 1, 존재하지 않으면 0으로 표기

 

무방향(양방향)그래프의 경우 두 노드 간 간선이 두개라고 볼 수 있으므로

인접행렬이 대각선 기준으로 대칭 구조

 

2. 인접리스트(연결리스트) (Adjacency List)

• 출발 노드 = 키
• 도착 노드(여러개 될 수 있으므로 리스트 형태) = 값

graph = {
    1 : [2, 3, 4],
    2 : [5],
    3 : [5],
    4 : [],
    5 : [6, 7],
    6 : [],
    7 : [3],
}

 

인접행렬 vs 인접리스트

• 차지하는 메모리 공간
  • 인접행렬 > 인접리스트 (n^2 > n)
• 시간
  • 인접행렬은 임의접근이 가능해서 비교적 빠름
  • 인접리스트는 특정 간선의 존재 여부 확인 위해서는 다 살펴봐야함 O(N)

문제에서 주어진 노드나 엣지의 수, 상황에 따라 적합한 선택지 적용

둘 다 사용할 수 있도록 연습하는 것이 좋음

 

 

🔷 그래프 순회

= 그래프 탐색(search)

• 그래프 순회 방법
  • DFS : 주로 스택 OR 재귀로 구현, 백트래킹
  • BFS : 주로 큐로 구현, 최단경로 문제

 

🔹 DFS(Depth First Search, 깊이 우선 탐색)

- 재귀로 구현

# dfs_재귀, 사전식 순서로 방문
def recursive_dfs(v, discovered = []):
    discovered.append(v)
    for w in graph[v]:
        if w not in discovered:
            discovered = recursive_dfs(w, discovered)
    return discovered
 
print(f'recursive_dfs : {recursive_dfs(1)}')    
# recursive_dfs : [1, 2, 5, 6, 7, 3, 4]

 

- 스택 반복으로 구현

# dfs_스택, 사전식 순서 역순으로 방문(stack으로 구현했기 때문)
def iterative_dfs(start_v):
    discovered = []
    stack = [start_v]
    while stack:
        v = stack.pop()
        if v not in discovered:
            discovered.append(v)
            for w in graph[v]:
                stack.append(w)
    return discovered
 
print(f'itertative_dfs : {itertative_dfs(1)}')    
# itertative_dfs : [1, 4, 3, 5, 7, 6, 2]

 

DFS는 완전탐색이기 때문에 모든 노드 다 살펴봄(브루트포스와 유사)

 

🔹  BFS (Breadth First Search, 넓이 우선 탐색)

최단경로 찾는 다익스트라 알고리즘 등에 매우 유용

 

- 큐를 이용한 반복으로 구현

# bfs_큐 반복
def iterative_bfs(start_v):
    discovered = [start_v]
    queue = [start_v]
    while queue:
        v = queue.pop(0)
        for w in graph[v]:
            if w not in discovered:
                discovered.append(w)
                queue.append(w)
    return discovered
 
print(f'iterative_bfs : {iterative_bfs(1)}')
# iterative_bfs : [1, 2, 3, 4, 5, 6, 7]

 

BFS는 재귀 구현 불가

 

🔹 DFS VS BFS

• 공통점 :  둘 다 완전탐색 그래프 탐색 알고리즘
• 차이점 : 탐색 순서
• 최단거리 문제에서 BFS는 목표 만나자마자 탐색 중단하고 최단거리임을 보장

 

 

🔷 백트래킹

해결책에 대한 후보를 구축해 나아가다 가능성이 없다고 판단되는 즉시 후보르 ㄹ포기해 정담을 찾아가는 알고리즘

DFS와 같은 방식으로 탐색하는 모든 방법 포함

DFS는 백트래킹의 골격을 이루는 알고리즘

주로 재귀로 구현

트리 가지치기 통해 탐색 최적화 가능

 

🔷 제약 충족 문제(Constraint Satisfaction Problems, CSP)

수많은 제약 조건을 충족하는 상태를 찾아내는 수학 문제

백트래킹은 제약 충족 문제 풀이에 필수 알고리즘

대표 문제 예시 : 스도쿠, 십자말풀이, 8퀸 문제, 4색 문제, 배낭 문제, 문자열 파싱, 조합 최적화 문제 등