암시적 그래프 구현과 명시적 그래프 구현

대충 320개의 노드를 가진 그래프 덩어리다. (C.elegans / Ref : MIT Dept of Brain Science)

Explict Graph

데이터를 저장할 공간을 직접 할당하여 정점과 간선을 기록하는 방식이다.

• 인접 행렬, 인접 리스트, 포인터 기반 연결 리스트를 통해서 직접 데이터를 구현하는 방식.
• A와 B가 연결되어있다라는 정보를 메모리에 물리적으로 저장하는 셈이다.
• 노드간의 관계를 직관적으로 파악할 수 있으나, 노드 수가 많아질수록 메모리 사용량이 아작난다. (O(V^2))

Implict Graph

데이터를 저장하는 데신, Rule/Function/Numbers...등을 통해 실시간으로 간선을 계산하는 방식이다.

• 수식이나 조건문을 이용해서 "표현"한다.
• 메모리에 간선 정보를 저장하지 않고, 탐색 과정에서 "다음 노드는 어디인가?"를 로직으로 산출한다.
• 메모리 효율이 아-주 좋고, Locality가 보장됨에 따라 Cache hit율이 좋아질 수 있다.
• 근데 이동 규칙이 유동적이면 안되는거다.

 

백준 1697. 그래프 이론이긴 한데

예시로 위 문제를 들어보자. 대충 Adjacent Matrix가 생각나지만... 행렬의 사이즈를 생각해보면 10e5^10e5 byte가 되니 대충 10기가 언저리 되시겠다. 근데 메모리 제한은 128MB인데?

 

그래서 배열을 사용해서 암시적으로 풀어야 한다. 그래프의 정의는 Vertex와 Edge의 쌍인 고로, 걍 리스트로 노드만 표현해보도록 하자. 근데 노드에 무슨 값을 집어 넣을지를 생각해야 하는데 - 위 문제 같은 경우의는 최단시간이 되시겠다. 상식적으로 최단 + 최단 = 최단이지 않겠는가? 아 물론 일반화를 하면 곤란하긴 한데....

 

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

using namespace std;

int dist[100001]; // 최단 시간을 저장할 배열 (메모리 약 400KB)

int main() {
    int N, K;
    cin >> N >> K;

    // 1. 초기화: 모든 거리를 -1로
    for(int i = 0; i <= 100000; i++) dist[i] = -1;

    queue<int> q;
    q.push(N);
    dist[N] = 0;

    while(!q.empty()) { // BFS
        int curr = q.front();
        q.pop();

        if(curr == K) {
            cout << dist[curr] << endl;
            break;
        }

        // 2. 이동 가능한 세 가지 경로
        int next_points[] = {curr - 1, curr + 1, curr * 2};
        
        for(int next : next_points) {
            // 범위 안에 있고, 아직 방문하지 않았다면 (-1이라면)
            if(next >= 0 && next <= 100000 && dist[next] == -1) {
                dist[next] = dist[curr] + 1; // 시간 갱신
                q.push(next); // 다음 방문지로 예약
            }
        }
    }
    return 0;
}

 

해서 이렇게 코드를 짜 볼 수 있겠다. BFS는 다녀간 곳을 체크해야 되고, Queue가 필요함을 상기하도록 하자.