[C++ - TIL] 그래프 구조의 이해와 DFS(깊이 우선 탐색) 및 탐욕 알고리즘

🎮 주제 : 그래프 구조의 이해와 DFS(깊이 우선 탐색) 및 탐욕 알고리즘

태그 : #C++ #알고리즘 #그래프 #DFS #탐욕알고리즘 #벡터 #자료구조

---

📌 학습 요약

• 탐욕 알고리즘 (Greedy Algorithm) : 매 순간 가장 좋아 보이는 선택을 반복하여 해답을 찾아가는 기법으로, 거스름돈 문제와 같은 상황에서 최적해를 구하는 원리 파악
• 그래프의 표현 (Adjacency List) : 정점 간의 연결 관계를 vector<vector<char>>를 이용한 인접 리스트로 구현하여 메모리 효율성 증대
• DFS (Depth First Search) : 재귀 함수와 메모리 스택의 원리를 결합하여 한 방향으로 끝까지 탐색하는 깊이 우선 탐색 알고리즘 습득
• 문자-인덱스 매핑 : 'A'와 같은 문자 데이터를 c - 'A' 연산을 통해 배열의 정수 인덱스로 변환하여 효율적으로 데이터를 관리하는 테크닉 활용
• STL Vector의 유연성 : push_back()과 resize()를 이용해 동적으로 정점과 간선을 추가하고 관리하는 C++ 표준 라이브러리 활용 능력 배양

---

🛠 주요 코드 및 구현 상세

1. 인접 리스트 기반 그래프 클래스 및 DFS 구현

class Graph {
private:
    vector<bool> visited;
    vector<vector<char>> adjacencyList;

public:
    // 1. 그래프 초기화: 정점 개수에 맞춰 벡터 크기 설정
    Graph(int size) {
        adjacencyList.resize(size);
        visited.resize(size, false);
    }

    // 2. 간선 추가: 무방향 그래프이므로 양방향으로 데이터 삽입
    void insert(char i, char j) {
        int from = i - 'A';
        int to = j - 'A';
        adjacencyList[from].push_back(j);
        adjacencyList[to].push_back(i);
    }

    // 3. 깊이 우선 탐색(DFS): 재귀 호출을 이용한 탐색
    void dfs(char node) {
        int idx = node - 'A';
        if (visited[idx]) return; // 이미 방문했다면 즉시 종료

        visited[idx] = true;      // 방문 처리
        cout << node << " ";

        // 인접한 이웃 노드들을 순차적으로 깊게 탐색
        for (char neighbor : adjacencyList[idx]) {
            dfs(neighbor);
        }
    }
};

---

✅ 주요 문법 및 개념 정리

개념 특징 주의 사항

탐욕 알고리즘	현재 단계에서의 최적 선택	항상 전체의 최적해를 보장하지는 않음
DFS	한 경로를 끝까지 파고든 후 복귀	무한 루프 방지를 위한 visited 체크 필수
Vector	동적 크기 조절 배열	vector와 같은 예약어를 변수명으로 사용 금지
인덱스 변환	char - 'A'로 숫자화	'A'~'Z' 범위를 벗어나는 문자에 주의

💡 로직 디테일 : while 조건의 미세한 차이

• money != 0 : 거스름돈이 정확히 0원이 될 때까지 계속 수행 (잔돈이 정확히 떨어질 때 적합)
• money >= 10 : 특정 단위(10원) 이상의 금액이 있을 때만 수행 (단위별 처리에 더 안전함)

---

✨ 느낀 점

• 그래프 구현 시 resize()를 통한 초기화 과정이 누락되면 런타임 에러가 발생하기 쉬우므로 초기 크기 설정의 중요성을 절감함
• 'A' - 'A'와 같은 간단한 산술 연산으로 문자를 인덱스로 다루는 방식이 코드의 직관성을 얼마나 높여주는지 경험함
• 재귀 함수가 호출될 때마다 메모리 스택에 정보가 쌓이는 과정을 이해하니 DFS의 탐색 흐름이 시각적으로 더 명확해짐
• 변수명 충돌(vector라는 이름을 변수명으로 사용 등)과 같은 사소한 실수가 디버깅 시간을 늘릴 수 있음을 배우며 명명 규칙의 중요성을 다시금 깨달음