C언어에서 그래프 탐색에 스택과 큐를 사용하는 방법

C언어에서 그래프 탐색은 다양한 응용에서 중요한 역할을 합니다. 특히 스택과 큐는 그래프 탐색 알고리즘인 DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)를 구현하는 데 핵심적인 데이터 구조입니다. 이 기사에서는 스택과 큐를 활용해 그래프 탐색을 수행하는 방법과 이를 효율적으로 구현하는 방법을 설명합니다. 그래프 탐색의 기초부터 스택과 큐의 구조적 이해, 그리고 이를 사용한 실제 알고리즘 구현까지 단계적으로 안내해 드립니다.

목차

그래프 탐색의 기본 개념


그래프 탐색은 그래프라는 데이터 구조에서 특정 노드(정점)부터 시작하여 연결된 모든 노드를 방문하는 과정을 의미합니다. 이는 컴퓨터 과학과 알고리즘에서 중요한 문제로, 다양한 응용 분야에서 활용됩니다.

그래프의 정의


그래프는 노드(정점)와 이를 연결하는 간선(엣지)으로 구성된 데이터 구조입니다. 간선의 방향 여부에 따라 방향 그래프와 무방향 그래프로 나뉘며, 간선에 가중치가 있으면 가중치 그래프로 분류됩니다.

그래프 탐색 알고리즘


그래프 탐색은 주로 다음 두 가지 알고리즘으로 수행됩니다:

  1. DFS(깊이 우선 탐색): 특정 경로를 따라 최대한 깊이 탐색한 뒤, 더 이상 탐색할 수 없을 때 이전 노드로 되돌아가는 방식입니다.
  2. BFS(너비 우선 탐색): 시작 노드에서 가까운 노드부터 차례대로 탐색하는 방식입니다.

그래프 탐색의 응용

  • 네트워크 경로 탐색
  • 퍼즐 해결(예: 미로 찾기)
  • 웹 크롤링
  • 소셜 네트워크 분석

그래프 탐색은 문제 해결에 있어 탐색의 범위와 깊이를 결정하는 중요한 도구입니다. 다음 섹션에서는 각각의 탐색 방식에 대해 자세히 살펴봅니다.

스택을 사용한 DFS(깊이 우선 탐색)


DFS(깊이 우선 탐색)는 그래프의 한 경로를 따라 최대한 깊이 이동한 뒤, 더 이상 진행할 수 없으면 이전 노드로 되돌아가는 탐색 방식입니다. 이 과정에서 스택이 중요한 역할을 합니다.

DFS의 동작 원리


DFS는 다음과 같은 순서로 동작합니다:

  1. 시작 노드를 스택에 삽입하고 방문 표시를 합니다.
  2. 스택의 맨 위 노드를 꺼내 연결된 미방문 노드를 탐색합니다.
  3. 새로운 노드를 발견하면 스택에 삽입하고 방문 표시를 합니다.
  4. 더 이상 방문할 노드가 없으면 스택에서 노드를 꺼냅니다.
  5. 스택이 비어 있을 때 탐색이 종료됩니다.

DFS의 장점

  • 경로 탐색이 필요한 문제(예: 미로 찾기)에 유리합니다.
  • 메모리 사용량이 상대적으로 적습니다(단, 재귀 호출 시 스택 오버플로우 주의).

C언어로 구현한 DFS

#include <stdio.h>
#include <stdbool.h>

#define MAX 100

int graph[MAX][MAX]; // 인접 행렬로 그래프 표현
bool visited[MAX];   // 방문 여부 확인
int stack[MAX];      // 스택 구현
int top = -1;        // 스택의 최상단

void push(int node) {
    stack[++top] = node;
}

int pop() {
    return stack[top--];
}

bool isEmpty() {
    return top == -1;
}

void dfs(int start, int n) {
    push(start);
    visited[start] = true;
    printf("Visited: %d\n", start);

    while (!isEmpty()) {
        int current = stack[top]; // 스택의 최상단 확인
        bool hasUnvisited = false;

        for (int i = 0; i < n; i++) {
            if (graph[current][i] == 1 && !visited[i]) {
                push(i);
                visited[i] = true;
                printf("Visited: %d\n", i);
                hasUnvisited = true;
                break;
            }
        }

        if (!hasUnvisited) {
            pop();
        }
    }
}

int main() {
    int n = 6; // 노드 개수
    // 그래프 초기화 (0 기반 인덱스)
    graph[0][1] = graph[1][0] = 1;
    graph[1][2] = graph[2][1] = 1;
    graph[1][3] = graph[3][1] = 1;
    graph[3][4] = graph[4][3] = 1;
    graph[4][5] = graph[5][4] = 1;

    // 방문 배열 초기화
    for (int i = 0; i < MAX; i++) visited[i] = false;

    // DFS 호출
    dfs(0, n);

    return 0;
}

DFS 구현에서의 주요 고려사항

  • 방문 표시: 이미 방문한 노드는 다시 탐색하지 않도록 관리해야 합니다.
  • 스택 오버플로우: 노드의 개수가 많을 경우 스택 오버플로우에 유의해야 합니다.

DFS는 경로 탐색과 백트래킹 문제에서 매우 유용하게 사용됩니다.

큐를 사용한 BFS(너비 우선 탐색)


BFS(너비 우선 탐색)는 시작 노드에서 가까운 노드부터 차례로 탐색하는 방식으로, 큐를 사용하여 구현됩니다. BFS는 최단 경로 탐색이나 그래프의 레벨 순회를 수행할 때 유용합니다.

BFS의 동작 원리


BFS는 다음과 같은 순서로 동작합니다:

  1. 시작 노드를 큐에 삽입하고 방문 표시를 합니다.
  2. 큐에서 노드를 꺼내 그 노드에 인접한 미방문 노드를 모두 큐에 삽입합니다.
  3. 이 과정을 큐가 빌 때까지 반복합니다.

BFS의 장점

  • 최단 경로를 보장하는 탐색 알고리즘입니다.
  • 트리 구조에서 특정 레벨의 모든 노드를 방문하는 데 유용합니다.

C언어로 구현한 BFS

#include <stdio.h>
#include <stdbool.h>

#define MAX 100

int graph[MAX][MAX]; // 인접 행렬로 그래프 표현
bool visited[MAX];   // 방문 여부 확인
int queue[MAX];      // 큐 구현
int front = -1, rear = -1; // 큐의 포인터

void enqueue(int node) {
    queue[++rear] = node;
}

int dequeue() {
    return queue[++front];
}

bool isEmpty() {
    return front == rear;
}

void bfs(int start, int n) {
    enqueue(start);
    visited[start] = true;
    printf("Visited: %d\n", start);

    while (!isEmpty()) {
        int current = dequeue();

        for (int i = 0; i < n; i++) {
            if (graph[current][i] == 1 && !visited[i]) {
                enqueue(i);
                visited[i] = true;
                printf("Visited: %d\n", i);
            }
        }
    }
}

int main() {
    int n = 6; // 노드 개수
    // 그래프 초기화 (0 기반 인덱스)
    graph[0][1] = graph[1][0] = 1;
    graph[1][2] = graph[2][1] = 1;
    graph[1][3] = graph[3][1] = 1;
    graph[3][4] = graph[4][3] = 1;
    graph[4][5] = graph[5][4] = 1;

    // 방문 배열 초기화
    for (int i = 0; i < MAX; i++) visited[i] = false;

    // BFS 호출
    bfs(0, n);

    return 0;
}

BFS 구현에서의 주요 고려사항

  • 큐의 초기화: 큐가 비어 있는지 확인하는 함수와 초기화 작업이 필요합니다.
  • 방문 표시: 큐에 삽입할 때 노드를 방문 처리해야 중복 방문을 방지할 수 있습니다.

BFS의 실제 응용

  • 최단 경로 탐색: 그래프에서 두 노드 간의 최단 경로를 탐색합니다.
  • 그래프의 연결 요소 탐색: 그래프가 몇 개의 연결 요소로 이루어져 있는지 찾을 수 있습니다.

BFS는 탐색의 범위를 점진적으로 확장하기 때문에 그래프 문제에서 매우 유용한 도구로 활용됩니다.

DFS와 BFS의 차이점과 선택 기준


DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)는 그래프 탐색에서 사용되는 두 가지 주요 알고리즘입니다. 각각의 탐색 방식은 장단점이 다르며, 문제 유형에 따라 적합성이 달라집니다.

DFS와 BFS의 주요 차이점

특징DFS(깊이 우선 탐색)BFS(너비 우선 탐색)
탐색 방식깊이 우선으로 경로를 따라 탐색너비 우선으로 레벨별 탐색
데이터 구조스택(재귀 호출 포함)
경로특정 경로를 따라가며 깊이 탐색최단 경로를 우선 탐색
메모리 사용적음 (단, 깊은 그래프에서는 스택 오버플로우 가능)많음 (큐 사용으로 인해 노드 저장 필요)
적합한 문제 유형미로 찾기, 백트래킹 문제최단 경로, 레벨 순회 문제

DFS와 BFS의 장단점

  1. DFS의 장점
  • 깊은 경로 탐색에 적합합니다.
  • 메모리를 적게 사용하며, 재귀적으로 간결하게 구현 가능합니다.
  1. DFS의 단점
  • 최단 경로를 보장하지 않습니다.
  • 깊은 그래프에서는 스택 오버플로우가 발생할 수 있습니다.
  1. BFS의 장점
  • 최단 경로 탐색에 적합합니다.
  • 그래프의 특정 레벨의 모든 노드를 탐색할 수 있습니다.
  1. BFS의 단점
  • 메모리 사용량이 큽니다.
  • 구현이 DFS에 비해 복잡할 수 있습니다.

알고리즘 선택 기준

  • 최단 경로가 중요한 경우: BFS를 선택합니다. 예를 들어, 미로에서 출구까지의 최단 경로를 찾는 문제에서는 BFS가 적합합니다.
  • 경로의 특정 패턴 탐색이 중요한 경우: DFS를 선택합니다. 예를 들어, 퍼즐 문제에서 가능한 모든 경로를 탐색해야 하는 경우 DFS가 적합합니다.
  • 그래프의 크기와 깊이: 깊이가 매우 깊은 그래프에서는 BFS가 더 안전합니다. DFS는 스택 오버플로우를 유발할 수 있습니다.

응용 사례

  • DFS: 게임 맵 탐색, 퍼즐 해결, 사이클 탐지
  • BFS: 소셜 네트워크 분석, 최단 경로 찾기, 네트워크 브로드캐스트

DFS와 BFS는 각각의 특성과 문제 유형에 맞게 적절히 선택하여 사용해야 합니다. 다음 섹션에서는 그래프를 표현하는 주요 방법인 인접 리스트와 인접 행렬을 살펴봅니다.

인접 리스트와 인접 행렬 구현


그래프를 표현하는 방식은 알고리즘의 효율성과 구현의 간결성에 영향을 미칩니다. 가장 일반적인 표현 방식은 인접 리스트와 인접 행렬입니다. 각 방식의 구조와 장단점을 이해하고, C언어로 구현하는 방법을 살펴보겠습니다.

인접 리스트


인접 리스트는 각 노드가 연결된 노드들의 목록으로 표현됩니다. 이는 연결된 노드만 저장하므로 메모리 사용이 효율적입니다.

  • 구조: 배열 또는 리스트를 사용하여 각 노드와 그 이웃 노드들을 저장합니다.
  • 장점:
  • 간선이 적은 희소 그래프에서 메모리 사용이 효율적입니다.
  • 특정 노드의 이웃 탐색이 빠릅니다.
  • 단점:
  • 두 노드 간의 연결 여부를 확인하려면 검색이 필요합니다.

C언어 구현 예제

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

typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

typedef struct {
    Node* head;
} Graph;

void addEdge(Graph* graph, int src, int dest) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = dest;
    newNode->next = graph[src].head;
    graph[src].head = newNode;

    newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = src; // 무방향 그래프의 경우
    newNode->next = graph[dest].head;
    graph[dest].head = newNode;
}

void printGraph(Graph* graph, int n) {
    for (int i = 0; i < n; i++) {
        Node* temp = graph[i].head;
        printf("Node %d: ", i);
        while (temp) {
            printf("%d -> ", temp->vertex);
            temp = temp->next;
        }
        printf("NULL\n");
    }
}

int main() {
    int n = 5; // 노드 개수
    Graph graph[n];
    for (int i = 0; i < n; i++) graph[i].head = NULL;

    addEdge(graph, 0, 1);
    addEdge(graph, 0, 4);
    addEdge(graph, 1, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 1, 4);
    addEdge(graph, 3, 4);

    printGraph(graph, n);

    return 0;
}

인접 행렬


인접 행렬은 2차원 배열로 그래프를 표현합니다. 노드 간의 연결 여부를 직관적으로 알 수 있습니다.

  • 구조: 2차원 배열에서 matrix[i][j]는 노드 ij 간의 연결 여부를 나타냅니다.
  • 장점:
  • 두 노드 간의 연결 여부를 O(1) 시간에 확인할 수 있습니다.
  • 구현이 간단하고 직관적입니다.
  • 단점:
  • 간선이 적은 희소 그래프에서는 메모리 낭비가 심합니다.
  • 특정 노드의 이웃 탐색에 O(n) 시간이 걸립니다.

C언어 구현 예제

#include <stdio.h>

#define MAX 5

void addEdge(int graph[MAX][MAX], int src, int dest) {
    graph[src][dest] = 1;
    graph[dest][src] = 1; // 무방향 그래프
}

void printGraph(int graph[MAX][MAX], int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            printf("%d ", graph[i][j]);
        }
        printf("\n");
    }
}

int main() {
    int graph[MAX][MAX] = {0};

    addEdge(graph, 0, 1);
    addEdge(graph, 0, 4);
    addEdge(graph, 1, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 1, 4);
    addEdge(graph, 3, 4);

    printGraph(graph, MAX);

    return 0;
}

인접 리스트 vs. 인접 행렬

특성인접 리스트인접 행렬
메모리 사용간선 수에 비례노드 수의 제곱에 비례
구현 복잡도상대적으로 복잡단순
연결 여부 확인느림 (O(E))빠름 (O(1))
이웃 노드 탐색빠름느림 (O(V))

인접 리스트는 메모리 효율성이 중요하거나 간선이 적은 희소 그래프에 적합하고, 인접 행렬은 간선이 많은 밀집 그래프에서 빠르게 연결 여부를 확인해야 할 때 적합합니다.

스택과 큐 구현 방법


스택과 큐는 DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)의 핵심 데이터 구조입니다. C언어에서는 배열이나 연결 리스트를 사용해 스택과 큐를 구현할 수 있습니다.

스택 구현


스택은 LIFO(Last In, First Out) 방식으로 동작합니다.

C언어 배열 기반 스택 구현 예제

#include <stdio.h>
#include <stdbool.h>

#define MAX 100

int stack[MAX];
int top = -1;

bool isStackEmpty() {
    return top == -1;
}

bool isStackFull() {
    return top == MAX - 1;
}

void push(int value) {
    if (isStackFull()) {
        printf("Stack Overflow\n");
        return;
    }
    stack[++top] = value;
}

int pop() {
    if (isStackEmpty()) {
        printf("Stack Underflow\n");
        return -1; // 에러 코드
    }
    return stack[top--];
}

int peek() {
    if (isStackEmpty()) {
        printf("Stack is empty\n");
        return -1; // 에러 코드
    }
    return stack[top];
}

int main() {
    push(10);
    push(20);
    push(30);

    printf("Top element: %d\n", peek());
    printf("Popped: %d\n", pop());
    printf("Popped: %d\n", pop());

    return 0;
}

큐 구현


큐는 FIFO(First In, First Out) 방식으로 동작합니다.

C언어 배열 기반 큐 구현 예제

#include <stdio.h>
#include <stdbool.h>

#define MAX 100

int queue[MAX];
int front = -1, rear = -1;

bool isQueueEmpty() {
    return front == rear;
}

bool isQueueFull() {
    return rear == MAX - 1;
}

void enqueue(int value) {
    if (isQueueFull()) {
        printf("Queue Overflow\n");
        return;
    }
    queue[++rear] = value;
}

int dequeue() {
    if (isQueueEmpty()) {
        printf("Queue Underflow\n");
        return -1; // 에러 코드
    }
    return queue[++front];
}

int peekFront() {
    if (isQueueEmpty()) {
        printf("Queue is empty\n");
        return -1; // 에러 코드
    }
    return queue[front + 1];
}

int main() {
    enqueue(10);
    enqueue(20);
    enqueue(30);

    printf("Front element: %d\n", peekFront());
    printf("Dequeued: %d\n", dequeue());
    printf("Dequeued: %d\n", dequeue());

    return 0;
}

스택과 큐의 비교

특성스택
동작 방식LIFO (마지막에 삽입된 요소 먼저 제거)FIFO (처음 삽입된 요소 먼저 제거)
주요 연산Push, Pop, PeekEnqueue, Dequeue, Peek
적용 사례DFS, 백트래킹BFS, 작업 스케줄링

응용에서의 주요 고려사항

  • 오버플로우와 언더플로우 처리: 배열 기반 구현에서는 경계 조건을 신중히 처리해야 합니다.
  • 메모리 효율성: 연결 리스트 기반 구현은 동적 메모리를 사용하여 공간을 절약할 수 있습니다.

스택과 큐는 그래프 탐색 외에도 여러 알고리즘에서 필수적인 역할을 하며, 구현 방법을 이해하면 다양한 문제를 효율적으로 해결할 수 있습니다.

그래프 탐색 알고리즘의 응용


그래프 탐색 알고리즘인 DFS와 BFS는 다양한 실제 문제에서 핵심적인 도구로 사용됩니다. 이를 통해 문제를 해결하고 최적화할 수 있는 주요 응용 사례를 살펴보겠습니다.

DFS의 응용 사례

1. 퍼즐 및 경로 탐색


DFS는 퍼즐 문제(예: 미로 찾기, 퍼즐 조합)에서 가능한 모든 경로를 탐색하거나 특정 경로를 찾아야 할 때 유용합니다.

  • 예시: 미로의 시작점에서 끝점까지 경로 탐색
  • 장점: 깊은 경로를 우선 탐색하므로 목표 지점까지 빠르게 도달 가능

2. 사이클 검출


DFS는 방향 그래프 또는 무방향 그래프에서 사이클 존재 여부를 확인하는 데 사용됩니다.

  • 알고리즘: 이미 방문한 노드를 다시 방문할 경우 사이클 존재
  • 응용 분야: 작업 의존성 그래프에서 무한 루프 검출

3. 강결합 요소 찾기


DFS는 방향 그래프에서 강결합 요소를 찾는 Kosaraju 알고리즘이나 Tarjan 알고리즘의 기반으로 활용됩니다.

  • 응용 분야: 소셜 네트워크 분석, 웹 크롤링

BFS의 응용 사례

1. 최단 경로 탐색


BFS는 모든 간선의 가중치가 동일한 그래프에서 두 노드 간의 최단 경로를 찾는 데 적합합니다.

  • 예시: 네트워크에서 최소 홉으로 통신 경로 찾기
  • 응용 분야: GPS 최단 경로 계산, 네트워크 라우팅

2. 레벨 탐색


BFS는 그래프의 각 레벨을 탐색하는 데 유용하며, 트리의 특정 깊이에 있는 모든 노드를 찾는 데도 사용됩니다.

  • 예시: 소셜 네트워크에서 사용자 추천 알고리즘 (2단계 이내 친구 찾기)

3. 그래프의 연결 요소 찾기


BFS는 그래프의 연결 요소를 탐색하여 그래프가 분리된 구성 요소로 이루어져 있는지 확인할 수 있습니다.

  • 응용 분야: 네트워크 안정성 분석, 군집 발견

DFS와 BFS의 통합 응용


두 알고리즘은 함께 사용하여 문제를 해결할 수도 있습니다.

  • 예시:
  • DFS로 특정 경로를 탐색하고 BFS로 최단 경로를 계산
  • 게임 AI에서 경로 탐색과 적응형 움직임 계산

응용 예제 코드: BFS로 최단 경로 탐색


다음은 BFS를 사용해 두 노드 간 최단 경로를 찾는 간단한 예제입니다:

#include <stdio.h>
#include <stdbool.h>

#define MAX 100
#define INF -1

int graph[MAX][MAX];
bool visited[MAX];
int distance[MAX];

void bfs(int start, int n) {
    int queue[MAX], front = -1, rear = -1;

    // 초기화
    queue[++rear] = start;
    visited[start] = true;
    distance[start] = 0;

    while (front != rear) {
        int current = queue[++front];

        for (int i = 0; i < n; i++) {
            if (graph[current][i] == 1 && !visited[i]) {
                queue[++rear] = i;
                visited[i] = true;
                distance[i] = distance[current] + 1; // 거리 계산
            }
        }
    }
}

int main() {
    int n = 6; // 노드 개수
    // 그래프 초기화 (0 기반 인덱스)
    graph[0][1] = graph[1][0] = 1;
    graph[1][2] = graph[2][1] = 1;
    graph[1][3] = graph[3][1] = 1;
    graph[3][4] = graph[4][3] = 1;
    graph[4][5] = graph[5][4] = 1;

    // 방문 배열 및 거리 배열 초기화
    for (int i = 0; i < MAX; i++) {
        visited[i] = false;
        distance[i] = INF;
    }

    bfs(0, n);

    // 결과 출력
    for (int i = 0; i < n; i++) {
        printf("Node %d: Distance from start = %d\n", i, distance[i]);
    }

    return 0;
}

그래프 탐색 알고리즘 선택 시 고려 사항

  • 문제의 목적: 최단 경로 탐색은 BFS, 깊은 경로 탐색은 DFS
  • 그래프 구조: 희소 그래프와 밀집 그래프에서의 메모리와 속도 고려
  • 실행 환경: 메모리 제한이 있는 경우 DFS의 재귀 호출에 주의

그래프 탐색 알고리즘의 활용은 문제 해결 능력을 크게 향상시키며, 다양한 실제 문제에 적용 가능합니다.

연습 문제와 해설


그래프 탐색 알고리즘에 대한 이해를 심화하기 위해 직접 구현해볼 수 있는 연습 문제와 해설을 제공합니다.

문제 1: 미로 탐색


설명
2차원 배열로 표현된 미로가 주어질 때, 시작점에서 끝점까지 도달할 수 있는지 확인하고 경로를 출력하는 프로그램을 작성하세요.

조건

  • 0은 이동 가능한 경로, 1은 벽을 의미합니다.
  • 시작점은 (0, 0), 끝점은 (n-1, m-1)입니다.
  • BFS를 사용하여 최단 경로를 탐색합니다.

입력 예시

5 6
0 1 0 0 0 0
0 1 0 1 1 0
0 0 0 1 0 0
1 1 1 1 0 1
0 0 0 0 0 0

출력 예시

Path exists: Yes
Shortest Path: (0,0) -> (0,2) -> (1,2) -> (2,2) -> (2,4) -> (3,4) -> (4,4) -> (4,5)

해설
BFS를 사용하여 각 노드(미로의 칸)의 부모 노드를 저장하며 탐색하면 최단 경로를 역추적할 수 있습니다.

문제 2: 연결 요소의 개수 구하기


설명
주어진 무방향 그래프에서 연결된 구성 요소(connected components)의 개수를 구하세요.

조건

  • 그래프는 인접 리스트로 주어집니다.
  • DFS를 사용하여 각 구성 요소를 탐색합니다.

입력 예시

노드 수: 6
간선 목록: 0-1, 1-2, 3-4

출력 예시

Number of connected components: 3

해설
DFS로 각 노드를 방문하며 구성 요소를 카운트합니다. 방문하지 않은 노드를 시작점으로 새 DFS를 호출하면 새로운 연결 요소가 발견됩니다.

문제 3: 방향 그래프에서 사이클 검출


설명
주어진 방향 그래프에서 사이클이 존재하는지 확인하세요.

조건

  • 그래프는 인접 리스트로 주어집니다.
  • DFS를 사용하여 방문 상태를 추적합니다.
  • 상태는 “미방문”, “방문 중”, “방문 완료”로 구분합니다.
  • 방문 중인 노드를 다시 방문할 경우 사이클이 존재합니다.

입력 예시

노드 수: 4
간선 목록: 0->1, 1->2, 2->0, 2->3

출력 예시

Cycle detected: Yes

해설
DFS로 각 노드를 탐색하며, 방문 중인 노드가 다시 탐색되는 경우 사이클이 있음을 확인합니다.

연습 문제 해설 코드: BFS 기반 최단 경로


다음은 문제 1(미로 탐색)을 해결하는 코드입니다:

#include <stdio.h>
#include <stdbool.h>

#define MAX 100
#define INF -1

int maze[MAX][MAX];
bool visited[MAX][MAX];
int distance[MAX][MAX];
int parent[MAX][MAX][2];

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

void bfs(int startX, int startY, int n, int m) {
    int queue[MAX][2], front = -1, rear = -1;

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

    while (front != rear) {
        int x = queue[++front][0];
        int y = queue[front][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 < m && maze[nx][ny] == 0 && !visited[nx][ny]) {
                queue[++rear][0] = nx;
                queue[rear][1] = ny;
                visited[nx][ny] = true;
                distance[nx][ny] = distance[x][y] + 1;
                parent[nx][ny][0] = x;
                parent[nx][ny][1] = y;
            }
        }
    }
}

연습 문제를 직접 해결하며 그래프 탐색 알고리즘의 동작을 깊이 이해해보세요!

요약


C언어에서 스택과 큐를 활용한 그래프 탐색은 DFS와 BFS 알고리즘을 통해 다양한 문제를 해결할 수 있는 강력한 도구입니다. 본 기사에서는 그래프 탐색의 기본 개념, DFS와 BFS의 구현 방법, 두 알고리즘의 차이점과 선택 기준, 그리고 실제 응용 사례를 다루었습니다. 이를 바탕으로 그래프 탐색 문제를 효율적으로 해결하는 능력을 키울 수 있습니다.

목차