11724 연결 요소의 개수 C++ 설명 및 풀이

안녕하세요 판타지코딩월드입니다!

 

오늘은 11724번 문제 연결 요소의 개수를 C++로 풀이해 보겠습니다.

---

 

1. 문제 설명

 

연결 요소의 개수는 처음 접하시는 분들은 그림으로 그려보면 이해가 편하다. 아래 그림을 먼저 참고해서 어떤 값을 구해야 하는지 이해하자.

 

<예시 입력>

 

1 2

2 3

3 1

4 5

 

연결 요소 예시

 

예시 입력이 위와 같을 때 연결 요소는 위와 같이 그릴 수 있다. 1, 2, 3이 연결되어 1개의 연결 요소가 생성되고, 4와 5가 연결되어 1개가 만들어져 2개의 연결 요소가 생성된다. 이와 같이 연결 요소의 개수를 세서 출력하는 것이 목표이다.

 

 

2. 풀이 방법

 

각 정점은 vector를 활용해서 연결해주면 된다. 그리고 dfs를 활용해서 정점을 탐색하면서 방문한 곳을 체크하여 두 번 방문하지 않도록 한다. 그렇게 처리하면 더 이상 방문해야 할 정점이 없을 때 dfs 함수는 종료된다. 이 때 바로 연결 요소의 개수를 1개 세어 준다. 이런식으로 나머지 정점도 탐색해 연결 요소의 개수를 세어 출력하면 된다.

 

• 입력 받기 : vector를 활용 해 연결

for(int i=0; i<M; i++)  // 연결의 개수 M 만큼 반복해서 입력 받음
{
    int u, v;
    cin >> u >> v;
    vec[u].push_back(v);
    vec[v].push_back(u);
}

 

코드 가장 첫 줄에 입력 받는 N과 M 중 연결 선의 개수인 M 만큼 반복하여 u와 v를 입력 받아 vector에 저장한다.

 

• 탐색 수행하기 : dfs활용하여 탐색하고, 연결 된 모든 정점을 방문하면 개수 1개 세어주기

for(int i=1; i<=N; i++)  // 1부터 정점의 개수 N만큼 반복해서 순서대로 방문 하기
{
    if(!check[i])  // 방문하지 않은 정점이면 dfs 함수를 실행하기
    {
        check[i] = true;
        dfs(i);
        cnt++;
    }
}

 

1부터 정점의 개수 N만큼 반복하여 방문하지 않은 정점을 발견하면 탐색을 시작한다. 연결된 모든 정점을 탐색하고 더 이상 방문할 정점이 없다면 개수를 1개 세어준다.

 

• dfs 함수로 연결된 모든 정점 방문하기 : 방문한 곳 true 처리하면서 연결 된 모든 정점 확인

void dfs(int start)  // 시작 정점을 인수로 받아 함수 실행
{
    for(int i=0; i<vec[start].size(); i++)  //해당 정점에 연결 된 정점 확인
    {
        int next = vec[start][i];
        if(!check[next])  // 방문하지 않은 정점이면 dfs 실행
        {
            check[next] = true;
            dfs(next);
        }
    }
}

 

시작 정점의 번호를 인수로 받아 연결 된 다른 정점을 방문한다. 연결된 정점은 next라는 변수에 담아 해당 정점에 방문한 적이 있는지 확인하고, 방문하지 않았다면 true 처리 후 해당 정점을 인수로 dfs함수를 실행한다.

 

 

3. 전체 코드

 

#include <iostream>
#include <vector>

using namespace std;

int N, M;
vector<int> vec[1001];
bool check[1001];
int cnt = 0;

void dfs(int start)
{
    for(int i=0; i<vec[start].size(); i++)
    {
        int next = vec[start][i];
        if(!check[next])
        {
            check[next] = true;
            dfs(next);
        }
    }
}

int main()
{
    cin >> N >> M;
    
    for(int i=0; i<M; i++)
    {
        int u, v;
        cin >> u >> v;
        vec[u].push_back(v);
        vec[v].push_back(u);
    }
    
    for(int i=1; i<=N; i++)
    {
        if(!check[i])
        {
            check[i] = true;
            dfs(i);
            cnt++;
        }
    }
    
    cout << cnt << endl;
    
    return 0;
}

---

오늘은 11724번 문제를 dfs를 활용하여 C++로 풀이해 보았습니다. vector에 정점을 저장하고, dfs로 탐색하면서 방문한 곳은 true 처리를 해 다시 방문하지 않도록 하여 몇 개의 연결 요소가 있는지 구하는 문제입니다. 정점을 저장하는 것과 dfs 활용 방법이 이해가 되셨다면 비슷한 다른 문제도 푸는데 도움이 될 것입니다.

 

감사합니다!