[C++ - TIL] 벡터의 수동 제어를 통한 다익스트라 인접 행렬 구현

🎮 주제 : 벡터의 수동 제어를 통한 다익스트라 인접 행렬 구현

태그 : #C++ #알고리즘 #다익스트라 #벡터 #메모리관리 #수동구현

---

📌 학습 요약

• 수동 크기 관리 : resize()와 같은 STL 멤버 함수 사용이 제한된 환경에서, 새로운 벡터 생성과 데이터 복사(Deep Copy)를 통해 배열의 크기를 동적으로 확장하는 저수준 제어 기법 습득
• 인접 행렬(Adjacency Matrix) 설계 : 노드 번호에 맞춰 행렬의 크기를 실시간으로 조정하고, 연결되지 않은 간선을 INFINITY로 초기화하여 다익스트라 알고리즘의 기초 토대 마련
• 데이터 보존 전략 : 그래프 확장 시 기존의 adjacencyMatrix, visited, distance 정보를 유실하지 않기 위해 일일이 루프를 돌며 값을 이전하는 번거롭지만 확실한 구현 방식 이해
• 인덱스 접근의 엄격함 : 초기화되지 않은 인덱스 접근 시 발생하는 런타임 에러를 방지하기 위해, 삽입되는 노드의 최대값(max(i, j) + 1)을 기준으로 선제적인 메모리 확보 로직 정립

---

🛠 주요 코드 및 구현 상세

1. 수동 resize()를 통한 메모리 확장 로직

void resize(int node) {
    newSize = node;

    // 1. 새로운 크기의 2차원 벡터 생성 및 INFINITY 초기화
    vector<vector<int>> newMatrix(newSize, vector<int>(newSize, INFINITY));
    for (int i = 0; i < size; ++i)
        for (int j = 0; j < size; ++j)
            newMatrix[i][j] = adjacencyMatrix[i][j]; // 기존 값 복사
    adjacencyMatrix = newMatrix;

    // 2. 방문 배열(visited) 수동 확장 및 복사
    vector<int> newVisited(newSize, 0);
    for (int i = 0; i < size; ++i)
        newVisited[i] = visited[i];
    visited = newVisited;

    // 3. 거리 배열(distance) 수동 확장 및 복사
    vector<int> newDistance(newSize, INFINITY);
    for (int i = 0; i < size; ++i)
        newDistance[i] = distance[i];
    distance = newDistance;

    size = newSize; // 최종 크기 업데이트
}

2. 조건부 확장 및 간선 삽입

void insert(int i, int j, int weight) {
    // 입력받은 노드 번호 중 큰 값을 기준으로 필요한 최소 크기 계산
    newSize = max(i, j) + 1;

    // 현재 할당된 크기보다 큰 노드가 들어오면 수동 확장 실행
    if (newSize > size) {
        resize(newSize);
    }

    adjacencyMatrix[i][j] = weight;
}

---

✅ 주요 문법 및 개념 정리

개념 특징 학습 포인트

인접 행렬	matrix[i][j] 형태의 2차원 구조	노드 간 연결 여부를 즉시**(O(1))** 확인 가능
수동 복사	루프를 통한 원소 일대일 대입	STL 함수의 편리함 뒤에 숨겨진 연산 과정을 체감
INFINITY	연결 없음(Disconnected)의 상징	다익스트라 갱신 시 비교 기준점이 됨
[] 연산자	직접적인 메모리 인덱스 접근	할당된 범위를 넘지 않도록 철저한 관리 필요

💡 핵심 인사이트 : STL 함수 제한의 교훈

• STL의 resize()는 내부적으로 이 과정을 자동화하여 최적화된 방식으로 처리합니다.
• 이를 직접 구현해 봄으로써 벡터가 단순한 배열 이상으로 메모리를 어떻게 재할당하고 관리하는지에 대한 저수준(Low-level) 이해도를 높일 수 있습니다.

---

✨ 느낀 점

• 벡터를 사용하면서도 그 강력한 멤버 함수들을 봉인하니, 평소에 얼마나 편리한 도구들을 당연하게 써왔는지 절실히 느낌
• 직접 복사 로직을 짜보며 데이터의 '이전(Migration)' 과정에서 발생할 수 있는 인덱스 오류나 초기화 누락을 디버깅하며 메모리 모델에 대한 이해가 깊어짐
• 실무에서는 비효율적일 수 있으나, 이러한 '바닥부터 구현하기' 경험이 나중에 복잡한 시스템 최적화나 라이브러리 분석 시 큰 자산이 될 것이라 확신함
• 단순한 알고리즘 구현을 넘어, 데이터 구조를 유연하게 관리하기 위한 설계적 고민을 할 수 있었던 유익한 시간이었음