[Silver II] 연결 요소의 개수 - 11724

문제 링크

성능 요약

메모리: 6532 KB, 시간: 76 ms

분류

그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색

제출 일자

2025년 10월 11일 21:19:12

문제 설명

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

출력

첫째 줄에 연결 요소의 개수를 출력한다.

제출

// 백준 11724

// - 아이디어
// [v] 간선을 입력받을때, 양쪽의 정점 리스트에 추가한다. 
// [v] 1~N까지 정점을 방문하며 재귀 DFS로 근접한 정점을 전부 방문한다.
// [v] 이때 VISITED로 이전 방문을 확인하고 RETURN FASLE
// [v] 최초 방문시 루프문으로 인접한 노드로 재귀 방문 후 RETRUN TRUE, 연결 요소 한개 발견마다 TRUE 1회
// [v] 메인에서 RETURN TRUE일때만 카운트하면 연결 요소의 개수 획득 가능

// - 시간복잡도
// 간선 읽어서 양쪽 정점리스트에 추가: M * 2
// 모든 정점을 한번씩 방문: N
// 방문여부 확인 후 DFS 재귀: N 
// (한번 방문한곳은 더이상 진행되지 않음, 한정점에 모든 정점이 연결된 경우라도, 1 + M으로 재귀 후, 나머지 N번 바로 RETURN FALSE : N+M)
// O(M+N) = O(N^2+N) = O(N^2) ,N = 10^3 N^2 = 10^6

// - 자료구조
// 정점별 간선벡터: vector<int>[]
// 방문 여부: bool[]

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>

int N,M;
std::vector<int> nodeArray[1001];
bool visited[1001];
void PushNode(int node, int edge);
bool DFS(int node);
int main()
{
	std::ios_base::sync_with_stdio(false);
	std::cin >> N >> M;
	
	for (int i = 0; i < M; i++)
	{
		int s, e;
		std::cin >> s >> e;
		PushNode(s, e);
		PushNode(e, s);
	}
	int count = 0;
	for (int i = 1; i < N+1; i++)
	{
		if (DFS(i) == true)
		{
			count++;
		}
	}
	std::cout << count;
}

inline void PushNode(int node, int edge)
{
	nodeArray[node].push_back(edge);
}

bool DFS(int node)
{
	if (visited[node])
		return false;

	visited[node] = true;

	auto it = nodeArray[node].begin();
	for (;it != nodeArray[node].end();++it)
	{
		int edge = *it;
		DFS(edge);
	}

	return true;
}

추가적인 생각

std::vector<int> nodeArray[1001];

필자는 각 정정에 연결된 정점들을 저장하는 자료구조를 인트 벡터의 고정 배열로 구현하였다. 정점의 최대갯수가 10^3이고, 간선의 최대갯수는 N*N*1/2로 10^6 이라고 생각해서 간선의 정보를 고정배열이 아닌 벡터로 해야겠다라고 생각하였는데, 잘 생각해보니 한 정점에서 나머지 정점간의 연결정보가 간선이니깐 정점들을 저장하는 자료구조도 벡터가 아닌 고정배열로 구현이 가능하였다.

이를테면 아래처럼 구현이 가능하다.

bool nodeBoard[1001][1001]; // 고정배열로 떡하니 박고
...
main{
    ...
    for // 루프
    {
        cin >> s >> e;
        nodeBoard[s][e] = true;
        nodeBoard[e][s] = true;
    }
}
...

void DFS(node){
    ...
	for (int i=1; i<=N; i++)
	{
        if (nodeBoard[node][i])
		    DFS(i);
	}
}