[SISS/C언어 스터디] 25-여름학기 2주차 스터디 - 깊이/너비 우선 탐색

[SISS/C언어 스터디] 25-여름학기 2주차 스터디 - 깊이/너비 우선 탐색

2학년 : Silver 5 이상, 3~4학년 : Silver 3 이상

자율 2문제를 풀어서 제출하면 됩니다.

백준 채점 확면 - 24479, 24444

 

 

24479

---

• 깊이 우선 탐색

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

#define MAX 200001

// 연결 리스트 노드
typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

Node* graph[MAX];      // 인접 리스트
bool visited[MAX];     // 방문 여부
int result[MAX];       // 방문 순서 저장
int order = 1;         // 순서 카운터
int n, m, k;

// 노드를 그래프에 추가
void add_edge(int u, int v) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = v;
    newNode->next = graph[u];
    graph[u] = newNode;
}

// 연결 리스트 정렬 (삽입 정렬)
void sort_adj_list(int u) {
    if (!graph[u] || !graph[u]->next) return;

    Node* sorted = NULL;
    Node* cur = graph[u];

    while (cur) {
        Node* next = cur->next;
        if (!sorted || cur->vertex < sorted->vertex) {
            cur->next = sorted;
            sorted = cur;
        } else {
            Node* temp = sorted;
            while (temp->next && temp->next->vertex < cur->vertex) {
                temp = temp->next;
            }
            cur->next = temp->next;
            temp->next = cur;
        }
        cur = next;
    }

    graph[u] = sorted;
}

// DFS
void dfs(int x) {
    visited[x] = true;
    result[x] = order++;

    Node* cur = graph[x];
    while (cur) {
        int y = cur->vertex;
        if (!visited[y]) {
            dfs(y);
        }
        cur = cur->next;
    }
}

int main() {
    scanf("%d %d %d", &n, &m, &k);

    for (int i = 0; i < m; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        add_edge(a, b);
        add_edge(b, a);
    }

    for (int i = 1; i <= n; i++) {
        sort_adj_list(i);
    }

    dfs(k);

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

    return 0;
}

 

2565

---

• 너비 우선 탐색

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

#define MAX 100001

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

typedef struct Queue {
    int data[MAX];
    int front, rear;
} Queue;

Node* graph[MAX];       // 인접 리스트
int visited[MAX];       // 방문 순서 저장
int N, M, R;            // 정점 수, 간선 수, 시작 정점
int Seq = 0;            // 방문 순서 카운터
Queue que;

// 큐 초기화
void init_queue() {
    que.front = que.rear = 0;
}

// 큐 삽입
void push(int x) {
    que.data[que.rear++] = x;
}

// 큐 삭제
int pop() {
    return que.data[que.front++];
}

// 큐 비었는지 확인
int empty() {
    return que.front == que.rear;
}

// 인접 리스트에 간선 추가
void add_edge(int u, int v) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = v;
    newNode->next = graph[u];
    graph[u] = newNode;
}

// 인접 리스트 정렬
void sort_list(int u) {
    Node* sorted = NULL;
    Node* current = graph[u];
    while (current) {
        Node* next = current->next;
        if (!sorted || current->vertex < sorted->vertex) {
            current->next = sorted;
            sorted = current;
        } else {
            Node* temp = sorted;
            while (temp->next && temp->next->vertex < current->vertex)
                temp = temp->next;
            current->next = temp->next;
            temp->next = current;
        }
        current = next;
    }
    graph[u] = sorted;
}

// BFS
void bfs(int n) {
    visited[n] = ++Seq;
    push(n);
    while (!empty()) {
        int u = pop();
        Node* cur = graph[u];
        while (cur) {
            int v = cur->vertex;
            if (!visited[v]) {
                visited[v] = ++Seq;
                push(v);
            }
            cur = cur->next;
        }
    }
}

int main() {
    scanf("%d %d %d", &N, &M, &R);
    for (int i = 0; i < M; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        add_edge(u, v);
        add_edge(v, u);
    }
    for (int i = 1; i <= N; i++) sort_list(i);

    init_queue();
    bfs(R);

    for (int i = 1; i <= N; i++) printf("%d\n", visited[i]);

    return 0;
}