탐색 - 12. 최종 프로젝트: 실전 문제 해결 (Final Project: Practical Problem Solving)

📌 12. 최종 프로젝트: 실전 문제 해결 (Final Project: Practical Problem Solving)

이제까지 배운 탐색 알고리즘을 활용하여 실제 문제를 해결하는 프로젝트를 수행합니다.
실제 개발 환경에서 탐색 알고리즘이 어떻게 적용되는지 이해하고, 실습을 통해 구현 능력을 향상시키는 것이 목표입니다.

---

💡 프로젝트 예제 1: 도서 관리 시스템

✔ 개요

도서 관리 시스템에서 해시 테이블(Hash Table)을 이용한 빠른 도서 검색 기능을 구현합니다.
도서 정보를 제목 또는 ISBN(국제 표준 도서번호) 기반으로 빠르게 탐색할 수 있도록 합니다.

🔍 핵심 기능

1. 도서 정보 추가 (Insert)
2. 도서 검색 (Search)
3. 도서 삭제 (Delete)

---

🔍 실습: 해시 테이블을 이용한 도서 검색

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define TABLE_SIZE 100

// 도서 정보 구조체
typedef struct Book {
    char title[50];
    int isbn;
    struct Book* next;
} Book;

Book* hashTable[TABLE_SIZE] = {NULL};

// 해시 함수
int hashFunction(int isbn) {
    return isbn % TABLE_SIZE;
}

// 도서 추가 함수
void insertBook(int isbn, char* title) {
    int index = hashFunction(isbn);
    Book* newBook = (Book*)malloc(sizeof(Book));
    newBook->isbn = isbn;
    strcpy(newBook->title, title);
    newBook->next = hashTable[index];
    hashTable[index] = newBook;
}

// 도서 검색 함수
Book* searchBook(int isbn) {
    int index = hashFunction(isbn);
    Book* current = hashTable[index];

    while (current) {
        if (current->isbn == isbn) return current;
        current = current->next;
    }
    return NULL;
}

// 도서 삭제 함수
void deleteBook(int isbn) {
    int index = hashFunction(isbn);
    Book* current = hashTable[index];
    Book* prev = NULL;

    while (current) {
        if (current->isbn == isbn) {
            if (prev) prev->next = current->next;
            else hashTable[index] = current->next;
            free(current);
            return;
        }
        prev = current;
        current = current->next;
    }
}

int main() {
    insertBook(12345, "C Programming");
    insertBook(67890, "Data Structures");
    insertBook(54321, "Algorithms in C");

    Book* found = searchBook(67890);
    if (found) printf("도서 찾음: %s (ISBN: %d)\n", found->title, found->isbn);
    else printf("도서를 찾을 수 없습니다.\n");

    deleteBook(67890);
    found = searchBook(67890);
    if (!found) printf("도서 삭제됨.\n");

    return 0;
}

📌 실행 결과

도서 찾음: Data Structures (ISBN: 67890)
도서 삭제됨.

✔ 해시 테이블을 이용하여 도서를 빠르게 검색 및 삭제 가능!

---

💡 프로젝트 예제 2: 길 찾기 프로그램

✔ 개요

• 그래프 탐색 알고리즘(DFS, BFS, 다익스트라)을 활용하여 길 찾기 기능을 구현
• 미로 같은 지도에서 출발점 → 목적지까지 최단 경로 찾기
• 다익스트라 알고리즘을 사용하여 가중치 그래프에서도 최적 경로 탐색

🔍 핵심 기능

1. 미로에서 최단 경로 찾기 (BFS)
2. 가중치 그래프에서 최적 경로 탐색 (다익스트라)

---

🔍 실습: BFS를 활용한 미로 길 찾기

#include <stdio.h>
#include <stdlib.h>

#define N 5

// 미로 (0: 이동 가능, 1: 벽)
int maze[N][N] = {
    {0, 1, 0, 0, 0},
    {0, 1, 0, 1, 0},
    {0, 0, 0, 1, 0},
    {1, 1, 1, 1, 0},
    {0, 0, 0, 0, 0}
};

// 방향 벡터 (상, 하, 좌, 우)
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

// BFS 탐색 함수
int BFS_maze(int startX, int startY, int endX, int endY) {
    int queue[N * N][2], front = 0, rear = 0;
    int visited[N][N] = {0};

    queue[rear][0] = startX;
    queue[rear][1] = startY;
    rear++;
    visited[startX][startY] = 1;

    while (front < rear) {
        int x = queue[front][0];
        int y = queue[front][1];
        front++;

        if (x == endX && y == endY) return 1;

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx >= 0 && nx < N && ny >= 0 && ny < N) {
                if (maze[nx][ny] == 0 && !visited[nx][ny]) {
                    queue[rear][0] = nx;
                    queue[rear][1] = ny;
                    rear++;
                    visited[nx][ny] = 1;
                }
            }
        }
    }
    return 0;
}

int main() {
    if (BFS_maze(0, 0, 4, 4)) {
        printf("길 찾기 성공!\n");
    } else {
        printf("길을 찾을 수 없습니다.\n");
    }
    return 0;
}

📌 실행 결과

길 찾기 성공!

✔ BFS를 이용하여 최단 경로 탐색 성공!

---

💡 프로젝트 예제 3: 간단한 AI 게임봇 (A 알고리즘)*

✔ 개요

• A 알고리즘을 이용하여 AI 게임봇이 최적 경로를 찾도록 구현*
• 게임 캐릭터가 장애물을 피하며 목적지까지 도달하는 방식

🔍 핵심 기능

1. A 알고리즘을 활용한 최적 경로 탐색*
2. 게임 개발에서 활용되는 탐색 로직 적용

✔ A 알고리즘은 이전에 설명한 코드를 활용 가능!*

---

📌 마무리 및 정리

프로젝트	사용된 알고리즘	핵심 개념
도서 관리 시스템	해시 테이블(Hash Table)	빠른 검색 및 삭제
길 찾기 프로그램	BFS / 다익스트라	최단 경로 탐색
AI 게임봇	A* 알고리즘	최적 경로 탐색

✔ 배운 탐색 알고리즘을 실제 프로젝트에 적용하여 문제 해결 능력 향상!
✔ 현실적인 데이터에서 탐색 알고리즘이 어떻게 활용되는지 경험 가능!