여기부터 비공개에서 공개로 전환해야 함 [C++ - TIL] STL을 활용한 템플릿 그래프 클래스와 DFS 구현

🎮 주제 : STL을 활용한 템플릿 그래프 클래스와 DFS 구현

태그 : #C++ #알고리즘 #그래프 #DFS #STL #템플릿 #자료구조

---

📌 학습 요약

• 범용적 그래프 설계 : template <typename T>를 사용하여 정수(int), 문자(char), 문자열(string) 등 다양한 데이터 타입을 지원하는 유연한 그래프 클래스 구현
• 현대적 인접 리스트 : unordered_map과 vector를 결합하여 노드의 추가와 인접 노드 관리가 용이한 인접 리스트 구조 구축
• 효율적인 방문 관리 : unordered_set의 해시 테이블 기반 탐색 특성을 활용하여 방문 여부를 O(1) 시간 복잡도로 빠르게 확인
• 재귀적 DFS 정립 : 깊이 우선 탐색의 흐름을 재귀 함수로 구현하고, count()와 find() 메서드의 차이점을 익혀 조건문 작성 능력 향상

---

🛠 주요 코드 및 구현 상세

1. 템플릿 기반 그래프 클래스와 DFS

template <typename T>
class Graph {
private:
    unordered_map<T, vector<T>> adjacencyList;
    unordered_set<T> visited;

public:
    // 1. 간선 추가 (양방향 연결)
    void insert(const T& i, const T& j) {
        adjacencyList[i].push_back(j);
        adjacencyList[j].push_back(i);
    }

    // 2. DFS 탐색 (재귀 방식)
    void search(const T& start) {
        // 방문 확인: count()는 존재하면 1, 없으면 0 반환
        if (visited.count(start)) return; 

        // 방문 기록 및 데이터 출력
        visited.insert(start);
        cout << start << " ";

        // 3. 인접 노드 순회
        for (const auto& element : adjacencyList[start]) {
            search(element); // 깊게 파고드는 재귀 호출
        }
    }
};

---

✅ 주요 문법 및 개념 정리

STL 메서드 반환값 및 특징 활용 사례

set.find(key)	존재 시 해당 위치 Iterator, 없으면 end()	값의 위치 정보가 필요할 때
set.count(key)	존재 시 1, 없으면 0 반환	단순히 존재 여부(T/F)만 확인할 때
unordered_map	해시 테이블 기반의 키-값 쌍 저장	인접 리스트의 노드 관리
template <T>	자료형을 매개변수화하여 일반화	데이터 타입에 독립적인 클래스 설계

💡 DFS의 핵심 : 방문 체크의 위치

• visited.insert(start)는 해당 노드를 출력하거나 인접 노드를 방문하기 직전에 수행되어야 합니다.
• 만약 이 로직이 잘못된 위치에 있으면 이미 방문한 노드를 다시 방문하여 **무한 루프(Infinite Loop)**에 빠질 위험이 있습니다.

---

✨ 느낀 점

• DFS 알고리즘이 재귀 호출을 통해 스택 프레임을 쌓아가며 깊게 탐색하는 과정을 시각적으로 이해하게 됨
• visited.insert()의 실행 타이밍이 알고리즘의 정석적인 동작에 얼마나 결정적인 영향을 미치는지 실습을 통해 체감함
• STL의 find()와 count()의 미묘한 차이를 정리하며 상황에 맞는 더 간결한 코드를 작성하는 법을 익힘
• 템플릿을 적용해 보니 하나의 코드로 여러 타입의 그래프를 처리할 수 있다는 점에서 객체지향 프로그래밍의 강력함을 느낌