C - [백준 11724 재구현] 연결 요소의 개수 (feat. 리스트)

 

전 포스트 참고

https://rnasterofmysea.tistory.com/48

 

 

 

그 전 포스트와 같은 문제를 다른 방식으로 구현해 보았습니다.

 

연결 요소의 개수(독립적인 그룹의 수)를 구하는 문제였는데 BFS 알고리즘을 동적 배열을 통해서 구현했는데 구조체 기반 리스트 형태로 구현하는 것에 대한 연습 + 차이점을 비교해보고자 추가적인 학습을 진행하였습니다.

 

 

---

코드

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

// 노드 구조체 정의
typedef struct Node {
    int vertex;             // 연결된 노드
    struct Node* next;      // 다음 노드 포인터
} Node;

// 전역 변수 선언
Node** graph;   // 그래프 배열 (인접 리스트를 위한 동적 배열)
int* visited;   // 방문 배열
int* queue;     // BFS 큐
int front = -1, rear = -1;

// 간선 추가 함수
void addEdge(int u, int v) {
    // u -> v 간선 추가
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = v;
    newNode->next = graph[u];
    graph[u] = newNode;
}

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

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

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

    while (front <= rear) {
        int current = dequeue();

        Node* temp = graph[current];  // 현재 노드와 연결된 노드 탐색
        while (temp) {
            if (!visited[temp->vertex]) {
                enqueue(temp->vertex);
                visited[temp->vertex] = 1;
            }
            temp = temp->next;  // 다음 노드로 이동
        }
    }
}

int main() {
    int N, M;  // 정점 개수 N, 간선 개수 M
    int result = 0; // 연결 요소 개수

    // 입력 받기
    scanf("%d %d", &N, &M);

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

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

    // 간선 입력
    for (int i = 0; i < M; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        u--; v--;  // 1-based -> 0-based 변환

        addEdge(u, v);  // 무방향 간선
        addEdge(v, u);  // 양방향 처리
    }

    // 연결 요소 찾기
    for (int i = 0; i < N; i++) {
        if (!visited[i]) {
            front = rear = -1;  // 큐 초기화
            bfs(i);
            result++;
        }
    }

    // 결과 출력
    printf("%d", result);

    // 메모리 해제
    for (int i = 0; i < N; i++) {
        Node* temp = graph[i];
        while (temp) {
            Node* next = temp->next;
            free(temp);
            temp = next;
        }
    }
    free(graph);
    free(visited);
    free(queue);

    return 0;
}

---

코드 동작 과정

1. 그래프 표현

• 그래프는 구조체 기반 인접 리스트를 사용해 표현됩니다.
• 노드의 연결 정보를 Node 구조체로 저장하며, 각 노드는 동적으로 메모리를 할당받습니다.

typedef struct Node {
    int vertex;             // 연결된 노드 번호
    struct Node* next;      // 다음 노드를 가리키는 포인터
} Node;

Node** graph;   // 각 노드의 연결 리스트를 저장할 배열

• graph[u]는 노드 uu에 연결된 노드들의 연결 리스트의 시작점을 가리킵니다.

---

2. 주요 함수

(1) addEdge

• 그래프에 간선을 추가하는 함수.
• u→vu \to v의 간선을 추가하기 위해 새로운 Node를 생성하고, 이를 graph[u] 리스트의 맨 앞에 삽입합니다.

void addEdge(int u, int v) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = v;        // 연결된 노드 번호
    newNode->next = graph[u];   // 기존 연결 리스트의 첫 노드
    graph[u] = newNode;         // 새로운 노드를 리스트의 첫 노드로 설정
}

(2) bfs

• BFS를 사용해 하나의 연결 요소를 탐색합니다.
• 큐를 사용하여 탐색을 수행하며, 방문한 노드는 visited 배열로 표시합니다.

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

    while (front <= rear) {     // 큐가 비어 있지 않을 동안 반복
        int current = dequeue();   // 큐에서 노드를 꺼냄

        // 현재 노드와 연결된 모든 노드를 탐색
        Node* temp = graph[current];
        while (temp) {
            if (!visited[temp->vertex]) {  // 방문하지 않은 노드라면
                enqueue(temp->vertex);    // 큐에 삽입
                visited[temp->vertex] = 1; // 방문 처리
            }
            temp = temp->next;  // 다음 노드로 이동
        }
    }
}

(3) enqueue / dequeue

• BFS에서 사용하는 큐를 구현합니다.
• 정적 배열을 사용해 큐의 동작을 구현하며, front와 rear를 이용해 큐의 삽입/삭제를 관리합니다.

---

3. main 함수

1. 입력 데이터 읽기
   • NN: 노드 개수.
   • MM: 간선 개수.
   • 그래프의 간선 정보를 읽어들여 인접 리스트에 저장합니다.

scanf("%d %d", &N, &M);

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

// 초기화
for (int i = 0; i < N; i++) {
    graph[i] = NULL;    // 인접 리스트 초기화
    visited[i] = 0;     // 방문 배열 초기화
}

// 간선 입력
for (int i = 0; i < M; i++) {
    int u, v;
    scanf("%d %d", &u, &v);
    u--; v--;            // 1-based -> 0-based 변환
    addEdge(u, v);       // u -> v 추가
    addEdge(v, u);       // v -> u 추가 (무방향 그래프)
}

1. 연결 요소 찾기
   • 각 노드를 순회하며 방문하지 않은 노드에서 BFS를 실행합니다.
   • BFS가 실행될 때마다 새로운 연결 요소를 발견한 것이므로, 결과 값을 증가시킵니다.

for (int i = 0; i < N; i++) {
    if (!visited[i]) {       // 방문하지 않은 노드에서 BFS 실행
        front = rear = -1;   // 큐 초기화
        bfs(i);              // BFS 실행
        result++;            // 연결 요소 개수 증가
    }
}

1. 결과 출력
   • 연결 요소의 개수를 출력합니다.

printf("%d", result);

1. 메모리 해제
   • 동적으로 할당된 인접 리스트의 모든 노드를 해제.
   • graph, visited, queue 배열도 해제.

for (int i = 0; i < N; i++) {
    Node* temp = graph[i];
    while (temp) {
        Node* next = temp->next;
        free(temp);
        temp = next;
    }
}
free(graph);
free(visited);
free(queue);

---

아래는 배열 기반과 리스트 기반 구현의 알고리즘 구조 차이를 비교한 표입니다.

 

항목	배열 기반	리스트 기반
그래프 표현	1차원 배열을 사용한 인접 행렬	구조체 기반의 연결 리스트 사용
간선 존재 확인	O(1)O(1)O(1) (배열 접근: graph[u * N + v])	O(Degree)O(\text{Degree})O(Degree) (리스트 순회)
간선 삽입	O(1)O(1)O(1) (배열 값 설정)	O(1)O(1)O(1) (리스트의 맨 앞에 삽입)
탐색	모든 노드와 간선을 순회 (O(N2)O(N^2)O(N2))	연결된 노드만 순회 (O(N+M)O(N + M)O(N+M))
메모리 구조	고정 크기 N2N^2N2 배열	동적 메모리 할당 (노드 수와 간선 수 기반)
적합한 그래프	밀집 그래프 (M≈N2M \approx N^2M≈N2)	희소 그래프 (M≪N2M \ll N^2M≪N2)

 

---

구조적 차이

배열 기반

if (!visited[i] && graph[current * N + i]) {
    enqueue(i);
    visited[i] = 1;
}

• 인접 행렬의 값(graph[u * N + v])을 직접 확인하여 간선 존재 여부를 판단.
• 간선 확인이 빠르지만, 모든 노드를 순회해야 함.

리스트 기반

Node* temp = graph[current];
while (temp) {
    if (!visited[temp->vertex]) {
        enqueue(temp->vertex);
        visited[temp->vertex] = 1;
    }
    temp = temp->next;
}

• 연결 리스트를 순회하며 간선 존재 여부를 판단.
• 연결된 노드만 탐색하므로 효율적이나, 간선 탐색 속도는 느림.

---

핵심 차이

1. 그래프 표현 방식:
   • 배열 기반은 모든 노드 쌍의 간선 정보를 저장.
   • 리스트 기반은 연결된 간선만 저장.
2. 탐색 방식:
   • 배열 기반은 모든 노드를 탐색하며 간선 여부를 확인.
   • 리스트 기반은 연결된 노드만 탐색.
3. 시간 복잡도:
   • 배열 기반: O(N2)O(N^2)로 고정.
   • 리스트 기반: O(N+M)O(N + M)로 간선 수에 따라 달라짐.