[코테 합격자 되기] 11장 그래프

# 그래프의 개념

그래프의 핵심 개념은 아래와 같다

노드: 정점

간선: 두 정점이 연결된 선

가중치: 거리와 같이 목적에 따라 간선에 가중치가 추가

순환(cycle): 간선들에 따라 계속 반복되는 순환 형태

 

---

 

# 그래프의 구현

1) 인접행렬

행과 열의 인덱스로 노드의 값을 나타내고, 배열의 값은 간선의 가중치가 된다

단점: 메모리 낭비 발생

장점: 간선여부 확인이 O(1)

사용 자료구조: 2차 array

예시 코드:

https://github.com/dremdeveloper/codingtest_cpp/blob/main/Algorithm_with_DataStructure/adjacencyarray.cpp

 

2) 인접리스트

특정 시작 노드를 기준으로 연결된 노드들을 리스트로 연결하는 방식이다

장점: 필요한 그래프의 노드 개수만큼만 추가되기에 메모리 낭비 발생 X

단점: 특정 노드에 많은 노드가 연결될 수록, 탐색 시 O(N)이 발생 (드문 케이스)

사용 자료구조: 2차 vector

예시 코드:

https://github.com/dremdeveloper/codingtest_cpp/blob/main/Algorithm_with_DataStructure/adjacencylist.cpp

 

3) 인접행렬 vs. 인접리스트

 

V를 정점 E를 간선이라고 하면,

위의 시/공간 복잡도를 가진다

 

특히, 인접리스트의 경우

특정 노드에 모든 노드가 연결되있으면

최악의 경우 O(E)가 발생한다 (물론, 매우 드문 케이스이다) 

 

4) 인접행렬 vs. 인접리스트 - 그래서 뭘 사용?

노드의 개수가 많을 때는 인접리스트를 사용해야 한다

(인접행렬을 사용하면, 메모리 초과 가능성이 있다)

 

반면, 특정 정점과 정점의 간선여부 혹은 간선의 가중치를

빠르게 알아내야 하는 경우가 많으면 인접행렬도 고려할만하다

 

그렇지만 대부분은 인접리스트를 사용하는 것이 좋다

 

---

 

# 그래프의 종류

대표적으로 DFS(깊이 우선탐색)와 BFS(너비 우선탐색)가 있다

- DFS

1) 개념

더 이상 탐색할 노드가 없을 때까지 일단 간다

더이상 탐색할 노드가 없으면 최근에 방문했던 노드로 퇴각 후, 가지 않은 노드를 방문한다

 

2) 구현해야 할 부분

1. 계속해서 깊이 탐색해야 함

2. 더 이상 길이 없으면, 가장 최근에 방문했던 노드로 퇴각 (방법: 재귀함수를 이용해 스택, 백트래킹 활용)

3. 이미 방문한 노드는 중복 방문하면 안 됨 (방법: visited vector 사용)

 

3) 예시 코드

#include <iostream>
#include <vector>

using namespace std;

// 전역 인접 리스트 및 방문 리스트
vector<vector<int>> adj;
vector<bool> visited;

// 그래프에 간선을 추가하는 함수
// 인자: v (정점), w (연결된 정점)
void add_edge(int v, int w) {
    adj[v].push_back(w); // 정점 v의 인접 리스트에 정점 w를 추가
}

// 깊이 우선 탐색(DFS)을 수행하는 함수
// 인자: v (현재 정점)
void dfs(int v) {
    // 현재 정점을 방문했다고 표시하고 출력
    visited[v] = true;
    cout << v << " ";

    // 현재 정점에 인접한 모든 정점을 순회
    for (int i = 0; i < adj[v].size(); ++i) {
        if (!visited[adj[v][i]]) {
            dfs(adj[v][i]);
        }
    }
}


// 메인 함수: 그래프 생성 및 DFS 수행
int main() {
    // 정점의 개수
    int V = 5;
    adj.resize(V);

    // 그래프에 간선 추가 (주어진 다이어그램에 따라)
    add_edge(0, 1); // A -> B
    add_edge(0, 2); // A -> C
    add_edge(1, 3); // B -> D
    add_edge(1, 4); // B -> E

    cout << "깊이 우선 탐색 (정점 0에서 시작):\n";
    
    visited.assign(V, false);
    dfs(0);
  /*
   재귀 호출 과정 설명 (예: 정점 0에서 시작):
    dfs(0) 호출 -> 0 출력
        dfs(1) 호출 -> 1 출력
            dfs(3) 호출 -> 3 출력
            dfs(4) 호출 -> 4 출력
        dfs(2) 호출 -> 2 출력
    - dfs_traversal 종료
  */

    return 0;
}

/*
 깊이 우선 탐색(DFS)의 개념:
 - DFS는 그래프 탐색 알고리즘 중 하나로, 시작 정점에서 출발하여 한 방향으로 가능한 깊이까지 탐색한 후,
   더 이상 갈 곳이 없으면 이전 정점으로 되돌아와 다른 방향으로 탐색을 계속하는 방식이다.
 - 시간 복잡도는 O(V + E)이며, 여기서 V는 정점의 수, E는 간선의 수를 의미한다.

 DFS를 사용해야 하는 경우:
 - 그래프의 모든 정점을 방문해야 하는 경우
 - 경로 찾기 (예: 미로 탐색)
 - 사이클 검출
 - 위상 정렬
 - 강한 연결 요소 찾기

 BFS를 사용할 수 없고 DFS를 사용해야 하는 경우:
 - 재귀적 성질을 이용해야 할 때 (예: 백트래킹 문제)
 - 공간 복잡도가 중요한 경우 (BFS는 큐를 사용하여 더 많은 메모리를 필요로 함)

*/

 

- BFS

1) 개념

현재 위치에서 가장 가까운 노드부터 방문하고 다음 노드로 넘어간다

모든 노드를 방문할 때까지 위 과정을 반복한다

 

2) 구현해야 할 부분

루트노드부터 시작해서, 가장 가까운 노드들부터 방문

가장 가까운 노드부터 방문하는 효율적인 방법은  

큐(FIFO)를 이용하는 것이다

 

맨 처음 시작 노드를 push 하고

아래의 과정을 반복하면 된다

본인이 pop 될 때, 본인 자식들을 push 하면 됨

 

또한, 중복 방문을 막기 위해서는

본인 자식들을 push 하기 전에

방문여부를 확인하고 통과되면, visited를 true로 해주면 된다

 

3) 예시 코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

// 전역 인접 리스트 및 방문 리스트
vector<vector<int>> adj;
vector<bool> visited;

// 그래프에 간선을 추가하는 함수
// 인자: u (정점), v (연결된 정점)
void add_edge(int u, int v) {
    adj[u].push_back(v); // 정점 u의 인접 리스트에 정점 v를 추가
}

// 너비 우선 탐색(BFS)을 수행하는 함수
// 인자: start (시작 정점)
void bfs(int start) {
    queue<int> q;
    visited[start] = true;
    q.push(start);

    while (!q.empty()) {
        int v = q.front();
        q.pop();
        cout << v << " ";

        for (int i = 0; i < adj[v].size(); ++i) {
            if (!visited[adj[v][i]]) {
                visited[adj[v][i]] = true;
                q.push(adj[v][i]);
            }
        }
    }
}

// 메인 함수: 그래프 생성 및 BFS 수행
int main() {
    // 정점의 개수
    int V = 5;
    adj.resize(V);

    // 그래프에 간선 추가 (주어진 다이어그램에 따라)
    add_edge(0, 1); // A -> B
    add_edge(0, 2); // A -> C
    add_edge(1, 3); // B -> D
    add_edge(1, 4); // B -> E

    cout << "너비 우선 탐색 (정점 0에서 시작):\n";
    bfs(0);
  
/*  
 BFS 호출 과정 설명 (예: 정점 0에서 시작):
 1. bfs(0) 호출 -> 0 출력, 인접 정점 1과 2를 큐에 추가
 2. 큐에서 1을 꺼내어 출력 -> 인접 정점 3과 4를 큐에 추가
 3. 큐에서 2를 꺼내어 출력 -> 인접 정점 없음
 4. 큐에서 3을 꺼내어 출력 -> 인접 정점 없음
 5. 큐에서 4를 꺼내어 출력 -> 인접 정점 없음
 6. 큐가 비어 있으므로 탐색 종료
*/

    return 0;
}

/*
 너비 우선 탐색(BFS)의 개념:
 - BFS는 그래프 탐색 알고리즘 중 하나로, 시작 정점에서 출발하여 인접한 모든 정점을 먼저 탐색한 후,
   다음 깊이의 정점들을 탐색하는 방식이다.
 - BFS는 큐를 사용하여 구현되며, 시간 복잡도는 O(V + E)이다. 여기서 V는 정점의 수, E는 간선의 수를 의미한다.

 BFS를 사용해야 하는 경우:
 - 최단 경로를 찾아야 하는 경우 (예: 최단 경로 문제)
 - 레벨 순서 탐색을 해야 하는 경우 (예: 각 레벨별로 노드를 처리해야 하는 문제)
 - 사이클 검출 (무방향 그래프에서)

 DFS 대신 BFS를 사용해야 하는 경우:
 - 경로의 길이가 중요한 경우 (BFS는 최단 경로를 보장함)
 - 큐를 사용하여 더 적은 메모리로 처리가 가능한 경우 (특히 넓은 그래프에서)
 - 모든 정점을 같은 레벨에서 순서대로 처리해야 하는 경우
*/

 

- DFS vs BFS

메모리 사용량에서 BFS는 큐를 사용하기에

DFS보다 메모리 사용량이 높다

 

백트래킹을 사용해야 하면 DFS

ex. 스도쿠 (1~5를 사용해서 합이 10이 되는 모든 경우)

 

최적의 해를 보장해야 하면 BFS

ex. 시작지점에서 끝지점까지 가는데 최소 거리 보장

 

애매하면, DFS

 

---

 

# 최소경로 알고리즘 (다익스트라, 밸만포드)

- 방식

위의 그림처럼 진행된다

시작점을 정하고

시작점을 기준으로 최소경로를 만들어내는 방식이다

방문을 했는지 여부를 위한 visited vector,

최소비용을 저장하기 위한 distance vector,

이전노드를 저장하기 위한 previous vector를 사용한다

 

 

갱신을 위한 연산 개념

예시 (E를 후보노드로 하고 C노드의 값들을 갱신 여부 확인 및 갱신)

위의 두 그림을 보다시피

현재 후보노드까지의 최소비용 + 현재 후보노드에서 다음노드까지의 가중치를 더한 값이

현재 previous vector (이전노드)의 적힌 값보다 작은 경우에만

최소 비용과 직전 노드를 갱신을 한다

 

그리고

현재 최소비용이 낮은 순으로 모든 노드를 후보노드로 지정하면서 반복한다

이를 위해 최소비용이 낮은 순으로 정렬되는 우선순위 큐를 활용하면 된다

 

모든 과정을 끝내고

위의 그림처럼 역추적을 하면,

최단 거리 경로를 알 수 있고

최소비용의 합 (최단 거리)도 알 수 있다

 

- 주의점

1. 방문 여부는 visited vector를 통해 이용

2. 우선순위 큐(pair<int, int>(최소비용, 노드값) 형태로 넣어서 최소비용이 낮은 것 순으로 pop)를 이용한다

3. 시작점이 달라지면 새롭게 생성해야 한다

반면, 끝지점은 달라져도 시작점만 같다면 역추적을 통해 모두 최단거리를 찾을 수 있다

 

- 예시코드

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <limits>

using namespace std;

// 무한대를 나타내기 위해 사용되는 상수
const int INF = numeric_limits<int>::max();

// 전역 변수 선언
vector<vector<pair<int, int>>> graph; // 그래프를 인접 리스트 형태로 저장
vector<int> dist;                    // 각 노드까지의 최단 거리를 저장
vector<int> prev;                    // 각 노드의 직전 노드를 저장
vector<bool> visited;

// 다익스트라 알고리즘 함수
void dijkstra(int start) {
    int n = graph.size();        // 그래프의 노드 개수
    dist.assign(n, INF);         // 최단 거리 배열을 무한대로 초기화
    prev.assign(n, -1);          // 직전 노드 배열을 -1로 초기화
    dist[start] = 0;             // 시작 노드의 거리는 0으로 설정
    
    // 최소 힙 (우선순위 큐)을 사용하여 최단 거리를 찾음
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, start});         // 시작 노드를 큐에 추가
    
    // 초기 상태
    /*
    Initial state:
    Node:  A  B  C  D  E
    Dist:  0  INF  INF  INF  INF
    Prev:  -1  -1  -1  -1  -1
    */

    // 큐가 빌 때까지 반복
    while (!pq.empty()) {
        int d = pq.top().first;  // 현재 노드까지의 거리
        int u = pq.top().second; // 현재 노드
        pq.pop();                // 큐에서 제거
        
        // 현재 노드까지의 거리가 이미 더 짧은 경로가 있으면 무시
        if (visited[u]) continue;
        visitied[u] = true;

        // 현재 노드의 모든 인접 노드를 탐색
        for (const auto& edge : graph[u]) {
            int v = edge.first;   // 인접 노드
            int weight = edge.second; // 가중치
            
            // 더 짧은 경로를 발견한 경우
            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight; // 최단 거리 업데이트
                prev[v] = u;                // 직전 노드 업데이트
                pq.push({dist[v], v});      // 큐에 추가
            }
        }
    }
}

// 경로를 출력하는 함수 (재귀 호출 사용)
void printPath(int node) {
    if (node == -1) return;     // base case: 시작 노드에 도달
    printPath(prev[node]);      // 직전 노드로 재귀 호출
    cout << node << " ";        // 현재 노드 출력
}

// 다익스트라 알고리즘 수행 과정 주석
/*
Initial state:
Node:  A  B  C  D  E
Dist:  0  INF  INF  INF  INF
Prev:  -1  -1  -1  -1  -1

1. A 노드 선택 (현재 최단 거리: 0)
- 인접 노드 B, C, E 업데이트:
After visiting A:
Node:  A  B  C  D  E
Dist:  0  4  4  INF  1
Prev:  -1  0  0  -1  0

2. E 노드 선택 (현재 최단 거리: 1)
- 인접 노드 C 업데이트:
After visiting E:
Node:  A  B  C  D  E
Dist:  0  4  3  INF  1
Prev:  -1  0  4  -1  0

3. C 노드 선택 (현재 최단 거리: 3)
- 인접 노드 B, D 업데이트:
After visiting C:
Node:  A  B  C  D  E
Dist:  0  4  3  11  1
Prev:  -1  0  4  2  0

4. B 노드 선택 (현재 최단 거리: 4)
- 인접 노드 업데이트 없음
After visiting B:
Node:  A  B  C  D  E
Dist:  0  4  3  11  1
Prev:  -1  0  4  2  0

5. D 노드 선택 (현재 최단 거리: 11)
- 인접 노드 B 업데이트:
After visiting D:
Node:  A  B  C  D  E
Dist:  0  4  3  11  1
Prev:  -1  0  4  2  0

최종 상태:
Node:  A  B  C  D  E
Dist:  0  4  3  11  1
Prev:  -1  0  4  2  0
*/

int main() {
    // 그래프를 인접 리스트 형태로 정의
    // 각 pair는 (인접 노드, 가중치)를 의미
    graph = {
        {{1, 4}, {2, 4}, {4, 1}},   // A (0)
        {},                         // B (1)
        {{1, 6}, {3, 8}},           // C (2)
        {{1, 2}},                   // D (3)
        {{2, 2}}                    // E (4)
    };

    int start = 0; // 시작 노드 (A)
    dijkstra(start); // 다익스트라 알고리즘 실행
    
    // 결과 출력
    cout << "Node\tDistance\tPath" << endl;
    for (int i = 0; i < dist.size(); ++i) {
        cout << i << "\t" << dist[i] << "\t\t";
        printPath(i);
        cout << endl;
    }
    
    return 0;
}

/*
다익스트라 알고리즘에 대한 설명:
1. 다익스트라 알고리즘의 개념:
   다익스트라 알고리즘은 가중치가 있는 그래프에서 특정 시작 노드로부터 다른 모든 노드까지의 최단 경로를 찾는 알고리즘입니다.
   이 알고리즘은 그래프의 모든 간선의 가중치가 양수일 때 유효합니다.

2. 다익스트라 알고리즘의 과정:
   1) 시작 노드의 거리를 0으로 설정하고, 나머지 노드의 거리는 무한대로 설정합니다.
   2) 모든 노드를 미방문 집합에 추가합니다.
   3) 현재 노드에서 인접한 모든 노드의 거리를 계산하여 더 짧은 경로가 발견되면 거리를 업데이트합니다.
   4) 현재 노드를 방문한 것으로 표시하고, 미방문 노드 중 최단 거리를 가진 노드를 선택하여 3) 과정을 반복합니다.
   5) 모든 노드를 방문할 때까지 3)과 4) 과정을 반복합니다.

3. 다익스트라 알고리즘의 시간 복잡도:
   - 인접 리스트를 사용한 구현: O((V+E)log V), 여기서 V는 노드의 개수, E는 간선의 개수입니다.
     (우선순위 큐를 사용하여 최소 거리를 찾고 업데이트하는데 log V 시간이 걸립니다)

4. 다익스트라 알고리즘의 한계:
   - 음수 가중치를 가진 간선이 있는 그래프에서는 동작하지 않습니다. 음수 가중치가 있는 경우 벨만-포드 알고리즘을 사용해야 합니다.

코드 실행 결과:
Node	Distance	Path
0	0		0 
1	4		0 1 
2	3		0 4 2 
3	11	0 4 2 3 
4	1		0 4 
*/

 

- 다익스트라의 문제점

음수 가중치가 있다면,

현재 기준 최소비용이라는 것이 무의미해지기에

다익스트라를 사용하면 안 되고 밸만-포드 알고리즘을 이용해야 한다