C - [백준 11724] 연결 요소의 개수 (feat. 배열)

참고 포스트

https://rnasterofmysea.tistory.com/47

https://rnasterofmysea.tistory.com/46

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

---

문제: 연결 요소의 개수 (BOJ 11724)

https://www.acmicpc.net/problem/11724

 

문제 설명

방향 없는 그래프가 주어졌을 때, 연결 요소(connected component)의 개수를 구하는 문제입니다.

• 정점의 개수(N): 1 ≤ N ≤ 1,000
• 간선의 개수(M): 0 ≤ M ≤ N × (N-1)/2
• 정점 번호는 1부터 N까지입니다.
• 입력으로 간선의 양 끝점을 나타내는 정수가 주어집니다.

입력

1. 첫 줄: 정점의 개수 N, 간선의 개수 M
2. 다음 M개의 줄: 간선의 양 끝점 u와 v

출력

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

예제 입력 1 

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

 

예제 1 출력 

2

 

예제 입력 2

6 8
1 2
2 5
5 1
3 4
4 6
5 4
2 4
2 3

 

예제 출력 2 

1

---

Checkpoint

 

1. 연결 요소의 의미

 

연결 요소의 개수는 그래프에서 서로 연결된 독립적인 그룹의 수를 나타냅니다.
각 연결 요소는 내부적으로 모든 정점이 연결되어 있지만, 다른 연결 요소와는 연결되지 않습니다.

(연결요소 = 독립적인 그룹)

 

연결 요소의 갯수 = 2

 

이미지 출처: https://velog.velcdn.com/images%2Festry%2Fpost%2F476bd587-f257-4ea6-8852-23894d585510%2F%EC%97%B0%EA%B2%B0%EC%9A%94%EC%86%8C.png

 

 

2. 기존의 BFS의 while문 반복 조건을 수정하였습니다.

 

while (front != rear) -> while (front <= rear)

 

while (front != rear)

• 의미: 큐의 front(읽는 위치)가 rear(쓰는 위치)와 같아지면 루프를 종료합니다.
• 문제점:
  • 이 조건은 큐에 하나의 요소가 남아있는 경우를 처리하지 못할 가능성이 있습니다.
  • 예를 들어, 큐에 하나의 요소만 있는 경우 front == rear가 되어 루프를 건너뛰고 마지막 요소를 처리하지 않습니다
• 해결방안: while (front <= rear)

---

코드 분석 및 풀이

접근 방식

1. 그래프 표현:
   • 입력을 통해 그래프를 인접 행렬로 표현합니다.
2. 탐색 방법:
   • BFS를 사용하여 한 연결 요소를 탐색합니다.
   • 방문하지 않은 노드에서 탐색을 시작하며, 탐색이 끝날 때마다 연결 요소의 개수를 증가시킵니다.

구현 코드

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

int *graph;
int *visited;
int *queue;
int front = -1;
int rear = -1;

void enqueue(int num) {
    queue[++rear] = num;
}

int dequeue() {
    return queue[++front];
}

void bfs(int start, int num_node) {
    enqueue(start);
    visited[start] = 1;
    while (front <= rear) {
        int current = dequeue();
        for (int i = 0; i < num_node; i++) {
            if (!visited[i] && graph[current * num_node + i]) {
                enqueue(i);
                visited[i] = 1;
            }
        }
    }
}

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

    visited = (int *)malloc(N * sizeof(int));
    graph = (int *)malloc(N * N * sizeof(int));
    queue = (int *)malloc(N * sizeof(int));

    for (int i = 0; i < N; i++) {
        visited[i] = 0;
    }

    for (int i = 0; i < N * N; i++) {
        graph[i] = 0;
    }

    int u, v = 0;
    for (int i = 0; i < M; i++) {
        scanf("%d %d", &u, &v);
        u--;
        v--;
        graph[u * N + v] = 1;
        graph[v * N + u] = 1;
    }

    for (int i = 0; i < N; i++) {
        if (!visited[i]) {
            front = -1;
            rear = -1;
            bfs(i, N);
            result++;
        }
    }

    printf("%d", result);

    free(queue);
    free(graph);
    free(visited);

    return 0;
}

코드 설명

1. 전역 변수 선언:
   • graph: 인접 행렬을 표현하는 1차원 배열입니다.
   • visited: 각 정점의 방문 여부를 저장합니다.
   • queue: BFS 탐색에서 사용할 큐입니다.
2. BFS 함수:
   • 큐를 사용하여 그래프를 탐색합니다.
   • 현재 노드와 연결된 모든 노드를 방문합니다.
3. 메인 함수:
   • 정점과 간선을 입력받아 인접 행렬을 구성합니다.
   • 각 노드를 확인하여 방문하지 않았다면 BFS 탐색을 수행하고 연결 요소의 개수를 증가시킵니다.

주요 포인트

• 인접 행렬 사용:
  • 간단한 구현이 가능하지만, 정점 수가 많아지면 메모리 사용량이 증가합니다.
  • 주어진 문제 조건(N ≤ 1,000)에서는 효율적입니다.
• 동적 메모리 할당:
  • 정점의 개수에 따라 배열 크기가 동적으로 결정되므로 malloc을 사용했습니다.
• BFS 탐색:
  • 큐를 사용하여 구현했으며, enqueue와 dequeue 함수로 큐의 연산을 캡슐화했습니다.