C - [백준 1260] DFS와 BFS

[참고 포스트]

https://rnasterofmysea.tistory.com/45

[자료구조 & 알고리즘] 그래프 + DFS

https://rnasterofmysea.tistory.com/46

[자료구조 & 알고리즘] 그래프 + BFS

 

C - [Backjoon 1260] DFS와 BFS 

 

예제 입력 1 

4 5 1
1 2
1 3
1 4
2 4
3 4

예제 출력 1 

1 2 4 3
1 2 3 4

예제 입력 2 

5 5 3
5 4
5 2
1 2
3 4
3 1

예제 출력 2

3 1 2 5 4
3 1 4 2 5

예제 입력 3

1000 1 1000
999 1000

예제 출력 3 

1000 999
1000 999

 

---

Checkpoint

1.

처음 입력 받은 그래프 배열을 DFS 와 BFS 에서 둘다 사용하기 위해 DFS는 재귀로 구현 BFS 는 큐(queue)로 구현하였다. (DFS를 stack으로 구현하기 위해서 구조체(struct)을 사용하여 Node를 생성해야한다.)

BFS를 큐로 구현할때도 구조체로 Node를 생성해서 구현하는 방법이 있으나 구조가 복잡해지므로 비교적 코드 구조가 간단한 배열을 사용했다.

2.

메모리를 효율적으로 사용하기 위해, 처음에 입력받는 정점 수, 간선 수, 시작 위치(N, M, V)를 입력 받은 후, 정점(노드)을 저장해놓는 graph,  방문 여부를 저장하는 visited, BFS를 위한 queue 변수는 동적메모리할당을 진행하였다.

3.

불필요한 메모리 낭비를 방지하기 위해  "1-based -> 0-based" 변환을 진행하였다. [문제에서 주어진 조건은 정점이 1부터 시작(1-based)하지만 배열을 생성하게 되면 0부터 시작(0-based)하기 때문에 문제의 1-based로 진행할경우 2차원 배열에서 행과 열이 각각 하나씩 낭비된다.(0~N열 0~N행). ]

---

DFS와 BFS를 활용한 그래프 탐색 (C언어 구현)

그래프 탐색 알고리즘은 컴퓨터 과학에서 중요한 개념 중 하나로, 노드와 간선으로 이루어진 그래프를 효율적으로 탐색하는 방법을 제공합니다. 이번 포스트에서는 **DFS(Depth First Search)**와 **BFS(Breadth First Search)**를 C언어로 구현하고, 코드의 작동 원리를 해설합니다.

---

문제 개요

입력 설명

1. 첫 번째 줄에 정점의 개수 N, 간선의 개수 M, 시작 노드 V가 주어집니다.
2. 두 번째 줄부터 M개의 줄에 걸쳐 각 간선이 연결하는 두 노드의 정보가 주어집니다. 간선은 양방향입니다.

출력 설명

1. 첫 줄에는 DFS(깊이 우선 탐색) 결과를 출력합니다.
2. 두 번째 줄에는 BFS(너비 우선 탐색) 결과를 출력합니다.

---

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

// 전역 변수 선언
int *graph;
int *visited;
int *queue;
int front = -1, rear = -1;

// 큐에 값 삽입
void enqueue(int num) {
    queue[++rear] = num;
}

// 큐에서 값 제거
int dequeue() {
    return queue[++front];
}

// DFS 함수
void dfs(int node, int num_node) {
    printf("%d ", node + 1);  // 1-based 출력
    visited[node] = 1;        // 방문 처리

    for (int i = 0; i < num_node; i++) {
        if (!visited[i] && graph[node * num_node + i]) {
            dfs(i, num_node);  // 연결된 노드로 이동
        }
    }
}

// BFS 함수
void bfs(int start, int num_node) {
    enqueue(start);
    visited[start] = 1;

    while (front != rear) {  // 큐가 비어 있지 않을 때까지 반복
        int current = dequeue();
        printf("%d ", current + 1);  // 1-based 출력

        for (int i = 0; i < num_node; i++) {
            if (!visited[i] && graph[current * num_node + i]) {
                enqueue(i);
                visited[i] = 1;
            }
        }
    }
}

int main() {
    int N, M, V;

    // 노드 수, 간선 수, 시작 노드 입력
    scanf("%d %d %d", &N, &M, &V);

    // 동적 메모리 할당
    graph = (int *)malloc(N * N * sizeof(int));  // 인접 행렬
    visited = (int *)malloc(N * sizeof(int));
    queue = (int *)malloc(N * sizeof(int));

    // 초기화
    for (int i = 0; i < N * N; i++) {
        graph[i] = 0;
    }
    for (int i = 0; i < N; i++) {
        visited[i] = 0;
    }

    // 간선 입력 (양방향 그래프)
    for (int i = 0; i < M; i++) {
        int num1, num2;
        scanf("%d %d", &num1, &num2);
        num1--;  // 1-based -> 0-based 변환
        num2--;
        graph[num1 * N + num2] = 1;
        graph[num2 * N + num1] = 1;  // 양방향 처리
    }

    // DFS 실행
    dfs(V - 1, N);
    printf("\n");

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

    // BFS 실행
    front = rear = -1;  // 큐 초기화
    bfs(V - 1, N);

    // 메모리 해제
    free(graph);
    free(visited);
    free(queue);

    return 0;
}

 

코드 설명

주요 데이터 구조

1. 인접 행렬 (Adjacency Matrix):
   • 그래프를 저장하기 위해 graph 배열을 사용합니다.
   • 노드 간의 연결 관계를 2차원 배열로 표현하지만, 효율성을 위해 1차원 배열을 사용합니다.
     • graph[i * N + j]는 노드 i와 j가 연결되었는지를 나타냅니다.
2. 방문 배열 (visited):
   • 이미 방문한 노드를 표시하기 위해 사용됩니다. 노드가 방문되었으면 1로 설정됩니다.
3. 큐 (queue):
   • BFS에서 탐색할 노드를 관리하기 위해 큐를 사용합니다. 배열로 구현되며, front와 rear로 큐의 시작과 끝을 관리합니다.

---

함수 구현

1. DFS (깊이 우선 탐색)

DFS는 재귀를 사용하여 그래프를 탐색합니다.

void dfs(int node, int num_node) {
    printf("%d ", node + 1);  // 현재 노드 출력 (1-based)
    visited[node] = 1;        // 방문 처리

    for (int i = 0; i < num_node; i++) {
        // 방문하지 않았고 연결된 노드가 있으면 재귀 호출
        if (!visited[i] && graph[node * num_node + i]) {
            dfs(i, num_node);
        }
    }
}

• 현재 노드를 출력한 뒤, 연결된 노드 중 방문하지 않은 노드를 재귀적으로 호출합니다.
• 재귀 호출이 끝나면 이전 호출로 되돌아가 탐색을 이어갑니다.

---

2. BFS (너비 우선 탐색)

BFS는 큐를 사용하여 그래프를 탐색합니다.

void bfs(int start, int num_node) {
    enqueue(start);           // 시작 노드를 큐에 추가
    visited[start] = 1;       // 방문 처리

    while (front != rear) {   // 큐가 비어 있지 않을 때까지 반복
        int current = dequeue();
        printf("%d ", current + 1);  // 현재 노드 출력 (1-based)

        for (int i = 0; i < num_node; i++) {
            if (!visited[i] && graph[current * num_node + i]) {
                enqueue(i);    // 연결된 노드를 큐에 추가
                visited[i] = 1;
            }
        }
    }
}

• 시작 노드를 큐에 넣고, 큐에서 노드를 하나씩 꺼내면서 탐색을 진행합니다.
• 연결된 모든 노드를 큐에 추가하며, 한 번 방문한 노드는 다시 방문하지 않습니다.

---

메인 함수

입력 처리 및 초기화

1. 노드 수(N), 간선 수(M), 시작 노드(V)를 입력받습니다.
2. 인접 행렬을 동적 메모리로 생성하고 모든 값을 0으로 초기화합니다.
3. 간선 정보를 입력받아 그래프에 저장합니다.

   graph[num1 * N + num2] = 1;
   graph[num2 * N + num1] = 1;  // 양방향 처리
   

탐색 실행

1. dfs()를 호출하여 DFS 탐색 결과를 출력합니다.
2. 방문 배열을 초기화한 뒤, bfs()를 호출하여 BFS 탐색 결과를 출력합니다.

메모리 해제

모든 동적 메모리(graph, visited, queue)를 해제합니다.

---

코드 실행 예시

입력

4 5 1
1 2
1 3
1 4
2 4
3 4

출력

1 2 4 3
1 2 3 4

동작 과정

1. DFS:
   • 시작 노드 1 → 2 → 4 → 3 순서로 탐색합니다.
2. BFS:
   • 시작 노드 1 → 2 → 3 → 4 순서로 탐색합니다.

---

핵심 포인트

1. DFS:
   • 깊이를 우선적으로 탐색하며, 재귀적으로 구현됩니다.
2. BFS:
   • 너비를 우선적으로 탐색하며, 큐를 사용하여 구현됩니다.
3. 인접 행렬:
   • 모든 노드의 연결 정보를 저장하여 탐색의 효율성을 높입니다.

 

추가 질문이나 코멘트가 있다면 댓글로 남겨주세요!