C언어로 DFS 구현하기

DFS(Depth-First Search)는 그래프나 트리를 탐색하는 알고리즘 중 하나로, 가능한 깊이까지 탐색한 후, 더 이상 탐색할 수 없으면 마지막 분기점으로 돌아가 다른 경로를 탐색하는 방식입니다. DFS는 주로 스택을 이용하여 구현되며, 재귀적인 방법으로도 쉽게 표현할 수 있습니다.

DFS의 동작 방식

1. 시작 정점을 방문하고, 해당 정점을 스택에 추가합니다.
2. 스택의 최상위 정점을 꺼내 그 정점과 연결된 모든 정점 중 아직 방문하지 않은 정점을 방문합니다.
3. 해당 정점을 스택에 추가하고, 다시 2번으로 돌아갑니다.
4. 스택이 비어있을 때까지 반복합니다.

C언어로 DFS 구현하기

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

#define MAX 100

// 그래프를 표현하기 위한 인접 리스트 구조체
typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

Node* adjList[MAX]; // 인접 리스트
int visited[MAX];   // 방문 여부를 기록하는 배열

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

// 그래프에 간선 추가 함수
void addEdge(int src, int dest) {
    Node* newNode = createNode(dest);
    newNode->next = adjList[src];
    adjList[src] = newNode;
}

// DFS 함수
void DFS(int vertex) {
    visited[vertex] = 1; // 현재 정점 방문 표시
    printf("%d ", vertex); // 방문한 정점 출력

    Node* temp = adjList[vertex];
    while (temp) {
        int connectedVertex = temp->vertex;
        if (!visited[connectedVertex]) {
            DFS(connectedVertex); // 재귀적으로 DFS 호출
        }
        temp = temp->next;
    }
}

int main() {
    // 그래프 초기화
    for (int i = 0; i < MAX; i++) {
        adjList[i] = NULL;
        visited[i] = 0;
    }

    // 간선 추가 (예: 0-1, 0-2, 1-3, 1-4, 2-5)
    addEdge(0, 1);
    addEdge(0, 2);
    addEdge(1, 3);
    addEdge(1, 4);
    addEdge(2, 5);

    printf("DFS 결과: ");
    DFS(0); // DFS 시작 정점

    return 0;
}

1. 그래프 표현: 인접 리스트를 사용하여 그래프를 표현합니다.
2. 간선 추가: addEdge 함수를 통해 간선을 추가합니다.
3. DFS 구현: DFS 함수는 재귀적으로 호출되며, 각 정점을 방문하고 연결된 정점을 탐색합니다.
4. 메인 함수: 그래프를 초기화하고 간선을 추가한 후, DFS를 시작합니다.

사용 예시

1. 경로 탐색: 특정 경로를 찾아야 할 때, 특히 모든 가능한 경로를 탐색할 필요가 있을 경우 유용합니다. 예를 들어, 미로 찾기 문제에서 DFS는 모든 경로를 탐색하여 출구를 찾을 수 있습니다.
2. 그래프의 연결 요소 찾기: 비연결 그래프에서 연결 요소를 찾는 데 유용합니다. DFS를 사용하여 모든 정점을 방문하면 각 연결 요소를 쉽게 파악할 수 있습니다.
3. 위상 정렬: 방향 그래프에서 위상 정렬을 수행할 때 DFS를 이용할 수 있습니다. 사이클이 없는 경우, DFS를 통해 정점을 방문하면서 후입선출(LIFO) 방식으로 정렬할 수 있습니다.
4. 백트래킹 문제: 조합 문제, 순열 생성, N-Queens 문제와 같은 백트래킹 문제에서 DFS는 후보 해를 탐색하는 데 적합합니다. 모든 가능한 조합을 시도하고, 조건에 맞지 않는 경우에는 되돌아가서 다른 경로를 탐색할 수 있습니다.
5. 메모리 사용: DFS는 스택을 사용하므로, 메모리 사용량이 상대적으로 낮습니다. 깊이가 깊은 그래프나 트리에서 메모리 효율이 중요한 경우에 DFS가 유리할 수 있습니다.
6. 해의 존재 여부 확인: DFS는 특정 조건을 만족하는 해가 존재하는지 확인하는 데 효과적입니다. 예를 들어, 특정 정점에 도달할 수 있는지를 확인하는 문제에서 DFS를 사용할 수 있습니다.

---

DFS를 사용해서 장애물 인식 프로그램을 구현할 수 있습니다.

Softeer - 현대자동차그룹 SW인재확보플랫폼

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

#define MAX_N 25

int map[MAX_N][MAX_N];
int visited[MAX_N][MAX_N];

int directions[4][2] = {
    {-1, 0}, // 상
    {1, 0},  // 하
    {0, -1}, // 좌
    {0, 1}   // 우
};

void dfs(int x, int y, int *count) {
    visited[x][y] = 1;  // 현재 위치 방문 표시
    (*count)++; // 장애물 수 증가

    // 네 방향으로 탐색
    for (int i = 0; i < 4; i++) {
        int newX = x + directions[i][0];
        int newY = y + directions[i][1];

        // 새로운 위치가 유효하고 장애물이며 방문하지 않았는지 확인
        if (newX >= 0 && newX < n && newY >= 0 && newY < n && 
            map[newX][newY] == 1 && !visited[newX][newY]) {
            dfs(newX, newY, count);
        }
    }
}

int main() {
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++){
        char tmp[n+1];
        scanf("%s", tmp);
        for(int j = 0; j < n; j++){
            map[i][j] = tmp[j] - '0'; //char을 int로 변환
            visited[i][j] = 0;
        }
    }

    int blockCount = 0;
    int blockSizes[MAX_N * MAX_N] = {0};

    // 맵을 탐색하여 블록 찾기
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (map[i][j] == 1 && !visited[i][j]) {
                int count = 0;
                dfs(i, j, &count); // 새로운 블록 크기 계산
                blockSizes[blockCount] = count;
                blockCount++;
            }
        }
    }

    // 블록 크기 오름차순 정렬
    for (int i = 0; i < blockCount; i++) {
        for (int j = i + 1; j < blockCount; j++) {
            if (blockSizes[i] > blockSizes[j]) {
                int temp = blockSizes[i];
                blockSizes[i] = blockSizes[j];
                blockSizes[j] = temp;
            }
        }
    }

    printf("%d\n", blockCount);
    for (int i = 0; i < blockCount; i++) {
        printf("%d\n", blockSizes[i]);
    }
    printf("\n");

    return 0;
}