Click here
Ver2.0 전체 열람

Ver2.0 그래프 알고리즘: DFS와 BFS 구현

재능넷
댓글 0 전체 26 페이지
콘텐츠 대표 이미지 - 그래프 알고리즘: DFS와 BFS 구현

그래프 알고리즘: DFS와 BFS 구현

코딩의 세계에서 가장 핵심적인 알고리즘을 파헤쳐 보자!

🚀 그래프 알고리즘의 세계로 출발~

안녕하세요 여러분! 오늘은 코딩 면접에서 단골로 나오는 그래프 알고리즘 중에서도 가장 기본이 되는 DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)에 대해 깊이있게 파헤쳐볼 거예요. 이 두 알고리즘은 진짜 개발자라면 꼭 알아야 하는 필수 개념이라 할 수 있죠! 😎

요즘 재능넷에서도 알고리즘 관련 강의나 코딩 과외 요청이 엄청 늘고 있다고 하더라구요. 특히 코딩 테스트 준비하시는 분들이 DFS/BFS 구현에 대해 많이 물어보신다고... ㅋㅋㅋ 그만큼 중요하다는 뜻이겠죠?

이 글을 다 읽고 나면 여러분도 그래프 알고리즘의 기초를 완벽하게 이해하고, C언어로 직접 구현할 수 있게 될 거예요. 어렵게만 느껴졌던 알고리즘이 사실은 꽤 재밌는 퍼즐 같다는 걸 느끼게 될 거예요! 진짜임 ㄹㅇ! 🔥

📚 그래프란 뭘까요? 기초부터 탄탄히!

그래프 알고리즘을 이해하기 전에 그래프가 뭔지부터 알아야겠죠? 그래프는 노드(Node)와 간선(Edge)으로 이루어진 자료구조예요. 노드는 정점(Vertex)이라고도 부르는데, 쉽게 말하면 점이고, 간선은 이 점들을 연결하는 선이라고 생각하면 됩니다.

우리 일상에서도 그래프는 정말 많이 볼 수 있어요:

  1. 소셜 네트워크: 사람들(노드)과 그들의 친구 관계(간선)
  2. 도로망: 교차로(노드)와 도로(간선)
  3. 웹페이지: 웹페이지(노드)와 하이퍼링크(간선)
  4. 지하철 노선도: 역(노드)과 선로(간선)

그래프는 크게 방향 그래프(Directed Graph)와 무방향 그래프(Undirected Graph)로 나눌 수 있어요. 방향 그래프는 간선에 방향이 있고, 무방향 그래프는 간선에 방향이 없어요. 인스타그램 팔로우 관계는 방향 그래프(내가 너를 팔로우해도 너는 나를 팔로우 안 할 수 있잖아요 ㅠㅠ), 페이스북 친구 관계는 무방향 그래프(서로 친구니까!)라고 볼 수 있죠.

A B C D 무방향 그래프 A B C D 방향 그래프

그래프는 인접 행렬(Adjacency Matrix)과 인접 리스트(Adjacency List) 두 가지 방식으로 표현할 수 있어요. 인접 행렬은 2차원 배열로 그래프를 표현하는 방식이고, 인접 리스트는 각 노드마다 연결된 노드들을 리스트로 저장하는 방식이에요.

🧩 인접 행렬 (Adjacency Matrix)

인접 행렬은 노드 간의 연결 관계를 2차원 배열로 표현해요. 노드가 n개라면 n×n 크기의 행렬이 필요하죠. 노드 i와 노드 j가 연결되어 있으면 matrix[i][j] = 1, 연결되어 있지 않으면 matrix[i][j] = 0으로 표시해요.

예를 들어, 위의 무방향 그래프를 인접 행렬로 표현하면 다음과 같아요:

// A, B, C, D 노드가 있는 무방향 그래프의 인접 행렬
int adjMatrix[4][4] = {
    {0, 1, 1, 0}, // A는 B, C와 연결
    {1, 0, 1, 1}, // B는 A, C, D와 연결
    {1, 1, 0, 1}, // C는 A, B, D와 연결
    {0, 1, 1, 0}  // D는 B, C와 연결
};

🧵 인접 리스트 (Adjacency List)

인접 리스트는 각 노드에 연결된 노드들을 리스트로 저장해요. 보통 배열의 각 인덱스가 노드를 나타내고, 해당 인덱스에는 연결된 노드들의 리스트가 저장되죠.

C언어에서는 연결 리스트를 사용하거나, 벡터 배열을 사용할 수 있어요. 하지만 C언어에는 벡터가 없으니 연결 리스트로 구현해볼게요:

// 노드 구조체 정의
typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

// 그래프 구조체 정의
typedef struct Graph {
    int numVertices;
    Node** adjLists;
} Graph;

// 노드 생성 함수
Node* createNode(int v) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}

// 그래프 생성 함수
Graph* createGraph(int vertices) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->numVertices = vertices;
    
    graph->adjLists = (Node**)malloc(vertices * sizeof(Node*));
    
    for (int i = 0; i < vertices; i++)
        graph->adjLists[i] = NULL;
    
    return graph;
}

// 간선 추가 함수 (무방향 그래프)
void addEdge(Graph* graph, int src, int dest) {
    // src에서 dest로 가는 간선 추가
    Node* newNode = createNode(dest);
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;
    
    // dest에서 src로 가는 간선 추가 (무방향 그래프이므로)
    newNode = createNode(src);
    newNode->next = graph->adjLists[dest];
    graph->adjLists[dest] = newNode;
}

위 코드로 그래프를 만들고 간선을 추가하는 방법은 다음과 같아요:

// 4개의 노드(0, 1, 2, 3)를 가진 그래프 생성
Graph* graph = createGraph(4);

// 간선 추가 (A=0, B=1, C=2, D=3 이라고 가정)
addEdge(graph, 0, 1); // A-B
addEdge(graph, 0, 2); // A-C
addEdge(graph, 1, 2); // B-C
addEdge(graph, 1, 3); // B-D
addEdge(graph, 2, 3); // C-D

인접 행렬과 인접 리스트는 각각 장단점이 있어요:

  1. 인접 행렬: 두 노드 간의 연결을 O(1) 시간에 확인할 수 있지만, 항상 n² 공간이 필요해요.
  2. 인접 리스트: 공간 효율성이 좋고(간선 수에 비례), 모든 인접 노드를 순회하기 쉽지만, 두 노드 간의 연결을 확인하는 데 O(degree) 시간이 필요해요.

보통 희소 그래프(간선이 적은 그래프)에서는 인접 리스트가, 밀집 그래프(간선이 많은 그래프)에서는 인접 행렬이 효율적이에요. 알고리즘 문제 풀 때는 대부분 인접 리스트를 많이 사용한다는 점! 기억해두세요~ 😉

🔍 DFS(깊이 우선 탐색)란?

DFS는 Depth-First Search의 약자로, 말 그대로 깊이를 우선으로 탐색하는 알고리즘이에요. 한 경로를 끝까지 탐색한 후에 다른 경로를 탐색하는 방식이죠.

DFS는 미로 찾기 같은 문제를 풀 때 유용해요. 한 길을 끝까지 가보고, 막히면 다시 돌아와서 다른 길을 시도하는 방식이니까요. 이런 방식을 '백트래킹(Backtracking)'이라고도 해요.

DFS의 동작 방식은 다음과 같아요:

  1. 시작 노드를 방문하고 방문 표시를 해요.
  2. 시작 노드와 인접한 노드 중 방문하지 않은 노드를 선택해요.
  3. 선택한 노드를 시작 노드로 삼아 다시 DFS를 수행해요(재귀 호출).
  4. 더 이상 방문할 노드가 없으면 이전 노드로 돌아가요.
A B C D E F G 1 2 3 4 5 6 7 DFS 탐색 순서: A → B → D → E → C → F → G

🧠 DFS의 구현 방법

DFS는 스택(Stack) 자료구조를 이용하거나 재귀 함수를 이용해 구현할 수 있어요. 재귀 함수를 사용하면 코드가 더 간결해지는데, 사실 재귀 함수는 내부적으로 시스템 스택을 사용하기 때문에 결국 스택을 사용하는 셈이죠.

먼저 재귀를 이용한 DFS 구현을 살펴볼게요:

// 방문 여부를 저장하는 배열
bool visited[MAX_VERTICES];

// 인접 행렬을 이용한 DFS
void DFS_Matrix(int adjMatrix[MAX_VERTICES][MAX_VERTICES], int v, int vertices) {
    // 현재 노드 방문 표시
    visited[v] = true;
    printf("%d ", v);
    
    // 인접한 모든 노드에 대해
    for (int i = 0; i < vertices; i++) {
        // v와 i가 연결되어 있고, i를 방문하지 않았다면
        if (adjMatrix[v][i] == 1 && !visited[i]) {
            DFS_Matrix(adjMatrix, i, vertices); // 재귀 호출
        }
    }
}

// 인접 리스트를 이용한 DFS
void DFS_List(Graph* graph, int v) {
    // 현재 노드 방문 표시
    visited[v] = true;
    printf("%d ", v);
    
    // 현재 노드의 인접 리스트 순회
    Node* temp = graph->adjLists[v];
    while (temp) {
        int adjVertex = temp->vertex;
        // 방문하지 않은 인접 노드라면
        if (!visited[adjVertex]) {
            DFS_List(graph, adjVertex); // 재귀 호출
        }
        temp = temp->next;
    }
}

이번엔 스택을 이용한 DFS 구현을 볼게요. 재귀를 사용하지 않는 방법이죠:

// 스택을 이용한 DFS (인접 리스트 사용)
void DFS_Stack(Graph* graph, int start) {
    // 방문 배열 초기화
    bool visited[MAX_VERTICES] = {false};
    
    // 스택 생성 및 시작 노드 푸시
    int stack[MAX_VERTICES];
    int top = -1;
    stack[++top] = start;
    
    while (top != -1) {
        // 스택에서 노드 하나를 꺼냄
        int v = stack[top--];
        
        // 이미 방문한 노드라면 건너뜀
        if (visited[v])
            continue;
        
        // 현재 노드 방문 표시
        visited[v] = true;
        printf("%d ", v);
        
        // 인접 노드들을 스택에 푸시 (역순으로)
        Node* temp = graph->adjLists[v];
        // 임시 배열에 인접 노드들을 저장
        int adjNodes[MAX_VERTICES];
        int count = 0;
        
        while (temp) {
            if (!visited[temp->vertex])
                adjNodes[count++] = temp->vertex;
            temp = temp->next;
        }
        
        // 역순으로 스택에 푸시 (DFS 순서를 맞추기 위해)
        for (int i = count - 1; i >= 0; i--)
            stack[++top] = adjNodes[i];
    }
}

스택을 이용한 방법이 재귀보다 좀 더 복잡해 보이지만, 재귀 호출이 많아질 경우 스택 오버플로우를 방지할 수 있다는 장점이 있어요. 특히 그래프가 매우 깊을 때 유용하죠!

ㅋㅋㅋ 근데 솔직히 코테에서는 재귀로 구현하는 게 훨씬 간단하고 실수할 확률도 적어서 재귀를 많이 쓰긴 해요. 스택 오버플로우가 걱정된다면 스택으로 구현하는 방법도 알아두면 좋겠죠?

⏱️ DFS의 시간 복잡도

DFS의 시간 복잡도는 그래프를 어떻게 표현하느냐에 따라 달라져요:

  1. 인접 행렬: O(V²), 여기서 V는 노드의 개수예요.
  2. 인접 리스트: O(V + E), 여기서 V는 노드의 개수, E는 간선의 개수예요.

대부분의 경우 인접 리스트를 사용하는 것이 더 효율적이에요. 특히 희소 그래프(간선이 적은 그래프)에서는 인접 리스트가 훨씬 효율적이죠.

🌊 BFS(너비 우선 탐색)란?

BFS는 Breadth-First Search의 약자로, 시작 노드에서 가까운 노드부터 탐색하는 알고리즘이에요. 같은 레벨(깊이)에 있는 노드들을 모두 방문한 후에 다음 레벨로 넘어가는 방식이죠.

BFS는 최단 경로 문제를 풀 때 유용해요. 특히 가중치가 없는 그래프(또는 모든 간선의 가중치가 동일한 그래프)에서 두 노드 간의 최단 경로를 찾을 때 BFS를 사용하면 정확한 결과를 얻을 수 있어요.

BFS의 동작 방식은 다음과 같아요:

  1. 시작 노드를 큐에 넣고 방문 표시를 해요.
  2. 큐에서 노드를 하나 꺼내고, 해당 노드와 인접한 노드 중 방문하지 않은 노드를 모두 큐에 넣고 방문 표시를 해요.
  3. 큐가 빌 때까지 2번 과정을 반복해요.
A B C D E F G 1 2 3 4 5 6 7 BFS 탐색 순서: A → B → C → D → E → F → G

🧠 BFS의 구현 방법

BFS는 큐(Queue) 자료구조를 이용해 구현해요. 재귀로는 구현하기 어려워요. 왜냐하면 BFS는 같은 레벨의 노드를 모두 방문한 후에 다음 레벨로 넘어가는 방식이기 때문이죠.

C언어로 BFS를 구현해볼게요:

// 큐 구현을 위한 구조체
typedef struct Queue {
    int items[MAX_VERTICES];
    int front;
    int rear;
} Queue;

// 큐 초기화
void initQueue(Queue* q) {
    q->front = -1;
    q->rear = -1;
}

// 큐가 비어있는지 확인
int isEmpty(Queue* q) {
    return q->rear == -1;
}

// 큐에 데이터 삽입
void enqueue(Queue* q, int value) {
    if (q->rear == MAX_VERTICES - 1)
        printf("Queue is full\n");
    else {
        if (q->front == -1)
            q->front = 0;
        q->rear++;
        q->items[q->rear] = value;
    }
}

// 큐에서 데이터 추출
int dequeue(Queue* q) {
    int item;
    if (isEmpty(q)) {
        printf("Queue is empty\n");
        item = -1;
    } else {
        item = q->items[q->front];
        q->front++;
        if (q->front > q->rear) {
            q->front = q->rear = -1;
        }
    }
    return item;
}

// 인접 행렬을 이용한 BFS
void BFS_Matrix(int adjMatrix[MAX_VERTICES][MAX_VERTICES], int start, int vertices) {
    bool visited[MAX_VERTICES] = {false};
    Queue q;
    initQueue(&q);
    
    // 시작 노드 방문 표시 및 큐에 삽입
    visited[start] = true;
    enqueue(&q, start);
    
    printf("BFS traversal: ");
    
    while (!isEmpty(&q)) {
        // 큐에서 노드 하나를 꺼냄
        int v = dequeue(&q);
        printf("%d ", v);
        
        // 인접한 모든 노드에 대해
        for (int i = 0; i < vertices; i++) {
            // v와 i가 연결되어 있고, i를 방문하지 않았다면
            if (adjMatrix[v][i] == 1 && !visited[i]) {
                visited[i] = true;
                enqueue(&q, i);
            }
        }
    }
    printf("\n");
}

// 인접 리스트를 이용한 BFS
void BFS_List(Graph* graph, int start) {
    bool visited[MAX_VERTICES] = {false};
    Queue q;
    initQueue(&q);
    
    // 시작 노드 방문 표시 및 큐에 삽입
    visited[start] = true;
    enqueue(&q, start);
    
    printf("BFS traversal: ");
    
    while (!isEmpty(&q)) {
        // 큐에서 노드 하나를 꺼냄
        int v = dequeue(&q);
        printf("%d ", v);
        
        // 현재 노드의 인접 리스트 순회
        Node* temp = graph->adjLists[v];
        while (temp) {
            int adjVertex = temp->vertex;
            // 방문하지 않은 인접 노드라면
            if (!visited[adjVertex]) {
                visited[adjVertex] = true;
                enqueue(&q, adjVertex);
            }
            temp = temp->next;
        }
    }
    printf("\n");
}

위 코드에서는 간단한 배열 기반 큐를 구현했어요. 실제로는 연결 리스트 기반 큐나 C 표준 라이브러리의 함수를 사용할 수도 있겠죠.

⏱️ BFS의 시간 복잡도

BFS의 시간 복잡도도 DFS와 마찬가지로 그래프 표현 방식에 따라 달라져요:

  1. 인접 행렬: O(V²), 여기서 V는 노드의 개수예요.
  2. 인접 리스트: O(V + E), 여기서 V는 노드의 개수, E는 간선의 개수예요.

역시 대부분의 경우 인접 리스트를 사용하는 것이 더 효율적이에요. 특히 희소 그래프에서는 인접 리스트가 훨씬 효율적이죠.

🤔 DFS와 BFS의 비교

DFS와 BFS는 각각 장단점이 있어요. 어떤 알고리즘을 선택할지는 문제의 특성에 따라 달라져요.

🔄 탐색 방식

DFS: 한 경로를 끝까지 탐색한 후 다른 경로를 탐색해요. 스택이나 재귀를 사용해요.

BFS: 시작 노드에서 가까운 노드부터 탐색해요. 큐를 사용해요.

🎯 적합한 문제 유형

DFS:

  1. 경로 존재 여부 확인
  2. 사이클 탐지
  3. 위상 정렬
  4. 연결 요소 찾기
  5. 미로 찾기

BFS:

  1. 최단 경로 찾기 (가중치가 없거나 모든 간선의 가중치가 동일한 경우)
  2. 네트워크 흐름 문제
  3. 연결 요소 찾기
  4. 두 노드 사이의 최소 간선 수 찾기
  5. 레벨 순서 탐색

🧠 메모리 사용

DFS: 재귀를 사용할 경우 호출 스택에 많은 메모리를 사용할 수 있어요. 그래프가 깊을수록 메모리 사용량이 증가해요.

BFS: 큐에 모든 노드를 저장해야 할 수 있어서 최악의 경우 많은 메모리를 사용할 수 있어요. 그래프가 넓을수록 메모리 사용량이 증가해요.

⏱️ 시간 복잡도

두 알고리즘 모두 인접 행렬을 사용할 경우 O(V²), 인접 리스트를 사용할 경우 O(V + E)의 시간 복잡도를 가져요.

재능넷에서 알고리즘 관련 강의를 찾아보면, DFS와 BFS는 항상 기본 중의 기본으로 다뤄지는 주제예요. 코딩 테스트나 기술 면접에서도 자주 나오는 주제니까 확실히 이해하고 넘어가는 게 좋아요! 😊

💻 실전 예제: 미로 탐색 문제

이제 DFS와 BFS를 활용한 실전 예제를 풀어볼게요. 가장 대표적인 문제 중 하나인 '미로 탐색' 문제를 살펴볼게요.

문제: N×M 크기의 미로가 있어요. 미로는 0(벽)과 1(길)로 이루어져 있어요. 시작 위치는 (0, 0)이고, 도착 위치는 (N-1, M-1)이에요. 시작 위치에서 도착 위치까지 가는 최단 경로의 길이를 구해보세요. (이동은 상하좌우로만 가능해요.)

이 문제는 BFS를 이용하면 쉽게 해결할 수 있어요. BFS는 시작 노드에서 가까운 노드부터 탐색하기 때문에, 도착 위치에 처음 도달했을 때의 경로가 최단 경로가 되거든요.

// 미로 탐색 문제 (BFS 이용)
#include <stdio.h>
#include <stdbool.h>

#define MAX_N 100
#define MAX_M 100

// 미로
int maze[MAX_N][MAX_M];
// 방문 여부
bool visited[MAX_N][MAX_M];
// 시작 위치에서의 거리
int distance[MAX_N][MAX_M];

// 상하좌우 이동을 위한 배열
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

// 큐 구현
typedef struct {
    int x, y;
} Point;

typedef struct {
    Point items[MAX_N * MAX_M];
    int front, rear;
} Queue;

void initQueue(Queue* q) {
    q->front = q->rear = 0;
}

bool isEmpty(Queue* q) {
    return q->front == q->rear;
}

void enqueue(Queue* q, int x, int y) {
    q->items[q->rear].x = x;
    q->items[q->rear].y = y;
    q->rear++;
}

Point dequeue(Queue* q) {
    Point p = q->items[q->front];
    q->front++;
    return p;
}

// BFS 함수
int bfs(int n, int m) {
    Queue q;
    initQueue(&q);
    
    // 시작 위치 초기화
    visited[0][0] = true;
    distance[0][0] = 1;
    enqueue(&q, 0, 0);
    
    while (!isEmpty(&q)) {
        Point current = dequeue(&q);
        int x = current.x;
        int y = current.y;
        
        // 도착 위치에 도달했다면
        if (x == n - 1 && y == m - 1)
            return distance[x][y];
        
        // 상하좌우 이동
        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 < m && maze[nx][ny] == 1 && !visited[nx][ny]) {
                visited[nx][ny] = true;
                distance[nx][ny] = distance[x][y] + 1;
                enqueue(&q, nx, ny);
            }
        }
    }
    
    // 도착 위치에 도달할 수 없는 경우
    return -1;
}

int main() {
    int n, m;
    
    // 미로 크기 입력
    scanf("%d %d", &n, &m);
    
    // 미로 입력
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &maze[i][j]);
        }
    }
    
    // BFS 수행
    int result = bfs(n, m);
    
    // 결과 출력
    printf("%d\n", result);
    
    return 0;
}

위 코드는 BFS를 이용해 미로의 최단 경로를 찾는 알고리즘이에요. 시작 위치에서부터 BFS를 수행하면서 각 위치까지의 거리를 계산하고, 도착 위치에 도달했을 때의 거리를 반환해요.

같은 문제를 DFS로도 풀 수 있지만, DFS는 최단 경로를 보장하지 않아요. DFS는 한 경로를 끝까지 탐색한 후 다른 경로를 탐색하기 때문에, 처음 도착 위치에 도달한 경로가 최단 경로가 아닐 수 있거든요. 그래서 이런 최단 경로 문제는 BFS가 더 적합해요!

🧩 그래프 알고리즘의 응용

DFS와 BFS는 다양한 문제를 해결하는 데 활용될 수 있어요. 몇 가지 응용 예를 살펴볼게요:

1. 연결 요소(Connected Component) 찾기

그래프에서 연결 요소란, 서로 연결된 노드들의 집합을 말해요. DFS나 BFS를 이용해 그래프의 모든 연결 요소를 찾을 수 있어요.

// 연결 요소 찾기 (DFS 이용)
void findConnectedComponents(Graph* graph, int vertices) {
    bool visited[MAX_VERTICES] = {false};
    int componentCount = 0;
    
    for (int i = 0; i < vertices; i++) {
        if (!visited[i]) {
            printf("Component %d: ", componentCount + 1);
            DFS_List(graph, i, visited);
            printf("\n");
            componentCount++;
        }
    }
    
    printf("Total number of connected components: %d\n", componentCount);
}

// 방문 배열을 매개변수로 받는 DFS
void DFS_List(Graph* graph, int v, bool visited[]) {
    visited[v] = true;
    printf("%d ", v);
    
    Node* temp = graph->adjLists[v];
    while (temp) {
        int adjVertex = temp->vertex;
        if (!visited[adjVertex]) {
            DFS_List(graph, adjVertex, visited);
        }
        temp = temp->next;
    }
}

2. 사이클 탐지(Cycle Detection)

그래프에서 사이클이란, 시작 노드로 돌아오는 경로를 말해요. DFS를 이용해 그래프에 사이클이 있는지 확인할 수 있어요.

// 사이클 탐지 (DFS 이용)
bool hasCycle(Graph* graph, int vertices) {
    bool visited[MAX_VERTICES] = {false};
    bool recStack[MAX_VERTICES] = {false}; // 재귀 스택
    
    for (int i = 0; i < vertices; i++) {
        if (!visited[i]) {
            if (isCyclicUtil(graph, i, visited, recStack))
                return true;
        }
    }
    
    return false;
}

bool isCyclicUtil(Graph* graph, int v, bool visited[], bool recStack[]) {
    if (!visited[v]) {
        visited[v] = true;
        recStack[v] = true;
        
        Node* temp = graph->adjLists[v];
        while (temp) {
            int adjVertex = temp->vertex;
            
            if (!visited[adjVertex] && isCyclicUtil(graph, adjVertex, visited, recStack))
                return true;
            else if (recStack[adjVertex])
                return true;
            
            temp = temp->next;
        }
    }
    
    recStack[v] = false; // 재귀 스택에서 제거
    return false;
}

3. 위상 정렬(Topological Sort)

위상 정렬은 방향 그래프에서 노드들을 선형으로 정렬하는 알고리즘이에요. 모든 간선 (u, v)에 대해 u가 v보다 앞에 오도록 정렬해요. DFS를 이용해 위상 정렬을 구현할 수 있어요.

// 위상 정렬 (DFS 이용)
void topologicalSort(Graph* graph, int vertices) {
    bool visited[MAX_VERTICES] = {false};
    int stack[MAX_VERTICES]; // 결과를 저장할 스택
    int top = -1;
    
    for (int i = 0; i < vertices; i++) {
        if (!visited[i]) {
            topologicalSortUtil(graph, i, visited, stack, &top);
        }
    }
    
    printf("Topological Sort: ");
    while (top != -1) {
        printf("%d ", stack[top--]);
    }
    printf("\n");
}

void topologicalSortUtil(Graph* graph, int v, bool visited[], int stack[], int* top) {
    visited[v] = true;
    
    Node* temp = graph->adjLists[v];
    while (temp) {
        int adjVertex = temp->vertex;
        if (!visited[adjVertex]) {
            topologicalSortUtil(graph, adjVertex, visited, stack, top);
        }
        temp = temp->next;
    }
    
    stack[++(*top)] = v; // 스택에 현재 노드 추가
}

4. 최소 신장 트리(Minimum Spanning Tree)

최소 신장 트리는 그래프의 모든 노드를 포함하면서 간선의 가중치 합이 최소인 트리를 말해요. Prim 알고리즘이나 Kruskal 알고리즘을 이용해 최소 신장 트리를 구할 수 있어요.

이런 응용 알고리즘들은 DFS와 BFS의 기본 개념을 확장한 것이에요. 기본 개념을 잘 이해하고 있다면, 이런 응용 알고리즘들도 쉽게 이해할 수 있을 거예요!

🚀 성능 최적화 팁

그래프 알고리즘을 구현할 때 성능을 최적화하기 위한 몇 가지 팁을 알려드릴게요:

1. 적절한 그래프 표현 방식 선택

그래프의 특성에 따라 적절한 표현 방식을 선택하세요:

  1. 간선이 많은 밀집 그래프: 인접 행렬
  2. 간선이 적은 희소 그래프: 인접 리스트

2. 방문 배열 최적화

방문 배열을 bool 타입으로 사용하면 메모리를 절약할 수 있어요. C언어에서는 stdbool.h 헤더를 포함시켜 bool 타입을 사용할 수 있어요.

3. 큐와 스택의 효율적인 구현

BFS에서 사용하는 큐와 DFS에서 사용하는 스택을 효율적으로 구현하세요. 배열 기반 구현은 간단하지만, 크기가 제한적이에요. 연결 리스트 기반 구현은 크기 제한이 없지만, 구현이 복잡해요.

4. 재귀 호출 최소화

DFS를 재귀로 구현할 경우, 그래프가 매우 깊으면 스택 오버플로우가 발생할 수 있어요. 이런 경우 반복문과 스택을 이용한 구현을 고려하세요.

5. 메모이제이션 활용

같은 노드를 여러 번 방문해야 하는 경우, 이전 계산 결과를 저장해두고 재활용하는 메모이제이션 기법을 활용하세요.

이런 최적화 팁들을 적용하면 그래프 알고리즘의 성능을 크게 향상시킬 수 있어요! 특히 대규모 그래프를 다룰 때 유용하죠.

🎯 실전 코딩 테스트 대비

코딩 테스트에서 그래프 알고리즘 문제는 자주 출제돼요. 특히 DFS와 BFS는 기본 중의 기본이죠. 코딩 테스트를 준비하는 분들을 위한 팁을 몇 가지 드릴게요:

1. 템플릿 코드 준비

DFS와 BFS의 기본 구현 코드를 템플릿으로 준비해두세요. 문제를 풀 때 이 템플릿을 기반으로 수정하면 시간을 절약할 수 있어요.

2. 그래프 표현 방식 숙지

인접 행렬과 인접 리스트 두 가지 방식 모두 구현할 수 있도록 연습하세요. 문제에 따라 더 적합한 방식을 선택할 수 있어야 해요.

3. 응용 문제 연습

단순한 DFS/BFS 구현을 넘어서, 연결 요소 찾기, 사이클 탐지, 위상 정렬 등의 응용 문제도 연습하세요.

4. 시간 복잡도 분석

구현한 알고리즘의 시간 복잡도를 분석하는 습관을 들이세요. 코딩 테스트에서는 시간 제한이 있기 때문에, 효율적인 알고리즘을 선택하는 것이 중요해요.

5. 경계 조건 처리

그래프가 비어있거나, 단일 노드만 있는 경우 등의 경계 조건을 처리하는 방법을 연습하세요.

요즘 재능넷에서도 코딩 테스트 대비 과외나 알고리즘 스터디 모집 글을 자주 볼 수 있어요. 함께 공부하면 더 효과적일 수 있으니, 관심 있으신 분들은 한번 찾아보세요! 🤓

📝 마무리

지금까지 그래프 알고리즘의 기초인 DFS와 BFS에 대해 알아봤어요. 두 알고리즘은 그래프 탐색의 기본이 되는 알고리즘으로, 다양한 문제 해결에 활용될 수 있어요.

정리하자면:

  1. DFS: 깊이 우선 탐색, 스택이나 재귀를 이용해 구현, 한 경로를 끝까지 탐색
  2. BFS: 너비 우선 탐색, 큐를 이용해 구현, 시작 노드에서 가까운 노드부터 탐색

두 알고리즘은 각각 장단점이 있어요. 문제의 특성에 따라 적절한 알고리즘을 선택하는 것이 중요해요. 최단 경로를 찾는 문제는 BFS가, 모든 경로를 탐색해야 하는 문제는 DFS가 더 적합할 수 있어요.

그래프 알고리즘은 코딩 테스트나 실제 개발 현장에서도 자주 활용되는 중요한 알고리즘이에요. 기본 개념을 확실히 이해하고, 다양한 문제를 풀어보면서 실력을 키워보세요!

이 글이 여러분의 그래프 알고리즘 학습에 도움이 되었길 바라요. 더 많은 알고리즘 지식이 필요하시다면 재능넷의 '지식인의 숲' 메뉴에서 다양한 주제의 글을 찾아보실 수 있어요. 또한 알고리즘 과외나 코딩 테스트 준비에 도움이 필요하시다면, 재능넷에서 관련 재능을 가진 분들을 만나보세요! 💪

알고리즘의 세계는 정말 넓고 깊어요. 오늘 배운 DFS와 BFS는 그 세계로 들어가는 첫 걸음일 뿐이에요. 계속해서 공부하고 성장하시길 바랄게요! 화이팅! 🚀

댓글 작성

이 글에 대한 여러분의 생각을 들려주세요

댓글 0
댓글을 불러오는 중입니다.

아직 댓글이 없습니다.

지식인의 숲 - 지적 재산권 보호 고지

지적 재산권 보호 고지

  1. 저작권 및 소유권: 본 컨텐츠는 재능넷의 독점 AI 기술로 생성되었으며, 대한민국 저작권법 및 국제 저작권 협약에 의해 보호됩니다.
  2. AI 생성 컨텐츠의 법적 지위: 본 AI 생성 컨텐츠는 재능넷의 지적 창작물로 인정되며, 관련 법규에 따라 저작권 보호를 받습니다.
  3. 사용 제한: 재능넷의 명시적 서면 동의 없이 본 컨텐츠를 복제, 수정, 배포, 또는 상업적으로 활용하는 행위는 엄격히 금지됩니다.
  4. 데이터 수집 금지: 본 컨텐츠에 대한 무단 스크래핑, 크롤링, 및 자동화된 데이터 수집은 법적 제재의 대상이 됩니다.
  5. AI 학습 제한: 재능넷의 AI 생성 컨텐츠를 타 AI 모델 학습에 무단 사용하는 행위는 금지되며, 이는 지적 재산권 침해로 간주됩니다.
Loading...