[C언어 깊이 우선 탐색 알고리즘] 깊이 우선 탐색 구현하기

💡 이번에는 깊이 우선 탐색을 구현 하는 법을 배워보았다.

문제

💡 깊이 우선 탐색을 구현하시오.

당연히 없는 문제기에 대충 내가 만들었다.

해답

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 1001

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

Node** a;
int n, m, c[MAX_SIZE];

void addFront(Node *root, int index) {
    Node *node = (Node*) malloc(sizeof(Node));
    node->index = index;
    node->next = root->next;
    root->next = node;
}

void dfs(int x) {
    if (c[x]) {
        return ;
    }

    c[x] = 1;
    printf("%d", x);

    Node *cur = a[x]->next;

    while (cur != NULL) {
        int next = cur->index;
        dfs(next);
        cur = cur->next;
    }
}

int main(void) {
    scanf("%d %d", &n, &m);
    a = (Node**)malloc(sizeof(Node*) * (MAX_SIZE));
    for (int i = 1 ; i <= n ; i++) {
        a[i] = (Node*)malloc(sizeof(Node));
        a[i]->next = NULL;
    }
    for (int i = 0 ; i < m ; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        addFront(a[x], y);
        addFront(a[y], x);
    }
    dfs(1);

    return 0;
}

설명

깊이 우선 탐색이란?

• 탐색을 함에 있어서 깊은 것을 우선으로 하여 탐색하는 알고리즘이다.
• 빠르게 모든 경우의 수를 탐색하고자 할 때 쉽게 사용할 수 있다.
• 스택(Stack) 자료구조에 기초한다.
• 깊이 우선 탐색은 𝑂(𝑁)의 시간이 소요된다.

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
2. 스택의 최상단 노드에게 방문하지 않은 인접 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리를 한다.
3. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
4. 2-3번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

패스트 캠퍼스

• 방문 및 노드 꺼냄 처리는 아래와 같다
  • 1 방문 → 2 방문 → 7 방문 → 6 방문 → 6 꺼냄 → 8 방문 → 8 꺼냄 → 7 꺼냄 → 2 꺼냄 → 3 방문 → 4 방문 → 5 방문 → 5 꺼냄 → 4 꺼냄 → 3 꺼냄 → 1 꺼냄

연결리스트 정의

#define MAX_SIZE 1001

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

Node** a;   // 정점이 여러개라고 가정하기 때문에 이차원 포인터로 할당
int n, m, c[MAX_SIZE];  // c는 방문을 했는지 확인하는 변수, n은 정점, m은 간선

addFront 함수

void addFront(Node *root, int index) {
    Node *node = (Node*) malloc(sizeof(Node));
    node->index = index;  // 노드의 인덱스는 인덱스이다.
    node->next = root->next;  // 노드의 다음은 루트의 다음을 가리킨다.
    root->next = node;  // 루트의 다음은 노드이다.
}

• 해당 함수로 가장 앞쪽에 붙을 수 있게 하여 스택 연결리스트처럼 만들었다.

dfs 함수

void dfs(int x) {

    // 현재 노드를 방문했다고 하면 return; 해줌
    if (c[x]) {
        return ;
    }
    // 방문 처리
    c[x] = 1;
    printf("%d", x);

    Node *cur = a[x]->next;

    while (cur != NULL) {
        int next = cur->index;
        dfs(next);
        cur = cur->next;
    }
}

• 깊이 우선 탐색 함수 이다.
• cur을 a[x]→next 로 정의해주고 cur 이 NULL이 아닐때까지 dfs() 를 재귀호출하여 방문처리 후 출력해준다.

main 함수

int main(void) {
    scanf("%d %d", &n, &m);
    a = (Node**)malloc(sizeof(Node*) * (MAX_SIZE));
    for (int i = 1 ; i <= n ; i++) {
        a[i] = (Node*)malloc(sizeof(Node));
        a[i]->next = NULL;
    }
    for (int i = 0 ; i < m ; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        addFront(a[x], y);  // x라는 정점에서 y로 갈수있다
        addFront(a[y], x);  // y라는 정점에서 x로 갈수있다
    }
    dfs(1);

    return 0;
}

• 첫번째 for문을 돌며 노드의 사이즈를 n 만큼 초기화 해준다.
• 두번째 for문을 돌며 addFront() 를 이용하여 연결리스트를 만들어준다.
  • addFront() 를 두번 해주는 이유는 x ↔ y로 갈수있게 해주기 위함이다.
• dfs() 함수를 실행한다.
  • 원소 1부터 깊이우선 탐색을 하기 때문에 인자 1을 넣어준다.
• 아래와같이 입력했다고 가정한다
  • 결과 : 1 → 3 → 2 방문
• 3 3 // n, m 1 2 // x, y 1 3 // x, y 2 3 // x, y

---

마치며..

main() 함수에서 입력한 값으로는 삼각형 모양의 트리가 나올 것이라고 생각하여 1 2 3 이라고 결과 값이 나올 것이라고 예상하였는데 1 3 2로 나와서 왜 그럴까 생각을 해보았는데 트리의 오른쪽부터 방문하는 것이 아닌가 싶다…

어렵다…