[C++ - TIL] 그래프 자료구조, 인접 행렬, 메모리 관리, 출력 등

🎮 주제 : 인접 행렬 그래프의 동적 확장 및 출력 시스템 구현

태그 : #C++ #자료구조 #그래프 #인접행렬 #연산자오버로딩 #메모리관리

---

📌 학습 요약

1. 그래프 구현의 고도화 : 정점 배열(vertex)과 간선 행렬(matrix)을 유기적으로 관리하며, 동적 배열의 재할당 원리를 통해 유연한 그래프 구조 설계
2. 동적 행렬 확장(resize) : 정점이 추가됨에 따라 인접 행렬의 크기도 함께 확장되어야 하며, 기존 연결 정보를 보존하면서 메모리 용량을 늘리는 기법 숙지
3. 초기화의 메커니즘 : 중괄호 초기화({0}) 시 첫 번째 원소 외의 나머지는 기본값(0)으로 채워지는 C++ 배열 초기화 규칙 명확히 이해
4. 사용자 정의 출력 시스템 : operator<< 연산자 오버로딩과 friend 키워드를 활용하여 cout << graph; 한 줄로 행렬 상태를 시각화하는 편의성 확보
5. 접근 제어 및 스트림 : 자식 클래스에 접근을 허용하는 protected의 용도와 ostream 객체를 통한 데이터 흐름 제어 복습

---

🛠 주요 코드 및 구현 상세

1. 정점 및 행렬의 동적 확장 (resize)

void resize(int newSize) {
    // 1. 새로운 정점 저장 공간 확보
    T* newVertex = new T[newSize];
    for (int i = 0; i < size; i++) newVertex[i] = vertex[i];

    // 2. 인접 행렬 재할당 로직 (정점 수 증가에 따른 n x n 확장)
    int** newMatrix = new int*[newSize];
    for (int i = 0; i < newSize; i++) {
        newMatrix[i] = new int[newSize]{0}; // 모든 관계 0으로 초기화
        if (i < size) {
            for (int j = 0; j < size; j++) {
                newMatrix[i][j] = matrix[i][j]; // 기존 연결 복사
            }
        }
    }

    // 3. 기존 메모리 해제 및 포인터 갱신
    // (기존 matrix 행별 delete[] 및 vertex delete[] 과정 포함)
    vertex = newVertex;
    matrix = newMatrix;
    capacity = newSize;
}

2. 그래프 시각화를 위한 연산자 오버로딩

// friend 전역 함수로 정의하여 private 멤버에 접근
friend ostream& operator<<(ostream& os, const Graph<T>& g) {
    os << "   ";
    for (int i = 0; i < g.size; i++) os << g.vertex[i] << "  ";
    os << endl;

    for (int i = 0; i < g.size; i++) {
        os << g.vertex[i] << "  "; // 행 이름 출력
        for (int j = 0; j < g.size; j++) {
            os << g.matrix[i][j] << "  ";
        }
        os << endl;
    }
    return os;
}

---

✅ 주요 문법 및 개념 정리

개념 특징 주의 사항

인접 행렬	정점 간 연결을 $O(1)$에 확인	정점이 많아질수록 $O(V^2)$ 공간 소모
중괄호 초기화	int a[5]{1}; → 1, 0, 0, 0, 0	모든 원소를 특정 값으로 채우지 않음
protected	자식 클래스에 멤버 노출	외부(main 등)에서는 여전히 접근 불가
friend	클래스 외부 함수에 특권 부여	캡슐화를 해칠 수 있으므로 신중히 사용

---

✨ 느낀 점

• 인접 행렬 그래프를 구현하며 단순히 데이터를 넣는 것을 넘어, 동적으로 변하는 메모리 상황(resize)을 관리하는 법을 익힘
• operator<< 오버로딩을 통해 복잡한 자료구조의 내부 상태를 직관적인 표 형태로 출력해보며 디버깅 효율성을 크게 높임
• 중괄호 초기화의 동작 방식을 정확히 정리하여 배열 할당 시 발생할 수 있는 초기값 오류를 예방할 수 있게 됨
• private과 protected의 차이를 명확히 이해하여 상속 구조에서의 데이터 보호 전략을 다시금 정립함