[BOJ/백준] 11724 연결 요소의 개수

● [문제번호 11724] 연결 요소의 개수

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

11724번: 연결 요소의 개수

 

● 알아야 할 것

: BFS

: DFS

: vector 자료구조와 메소드

 

● 풀이 과정

: 다음 조건을 만족하면 연결 요소가 될 수 있다. (참고)

조건 1. 연결 요소에 속한 모든 정점을 연결하는 경로가 있어야 한다.

조건 2. 또 다른 연결 요소에 속한 정점과 연결하는 경로가 있으면 안된다.

 

예를 들어 '예제 입력1' 을 그래프로 표현하면 다음과 같다.

1개 그래프 中 2개 연결 요소

 

따라서 하나의 정점에서 탐색을 시작해서 모든 정점을 방문하지 않는 경우를 생각해서

모든 정점을 출발 정점으로 확인해봐야한다.

 

: BFS든 DFS든 무엇을 선택하든 상관없다.

출력이나 다른 조건이 없기에 방문한 하면 되므로

기본적인 작성 형태로 구현하면 된다.

 

● 주의 할 것

:  하나의 정점에서 탐색을 시작해서 모든 정점을 방문하지 않는 경우를 생각해서

모든 정점을 출발 정점으로 확인해봐야한다.

 

● 참고 할 것

: 연결 요소 이해

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// vertex : 각 정점에 연결된 정점집합
// visited : 정점의 방문기록
vector<int> vertex[1001];
bool visited[1001];
int N, M, cnt;

// 넓이 우선 탐색
int bfs(int start)
{
    // 이미 방문한 출발 정점인 경우
    if(visited[start])
        return 0;
    
    // 전형적인 작성 형식
    // 출력없이 방문기록만 남기면 됨
    queue<int> q;
    
    visited[start] = true;
    q.push(start);
    
    while(!q.empty())
    {
        int from = q.front();
        q.pop();
        
        for(int i = 0; i < vertex[from].size(); i++)
        {
            int to = vertex[from][i];
            
            if(!visited[to])
            {
                visited[to] = true;
                q.push(to);
            }
        }
    }
    
    // 방문하지 않은 출발 정점인 경우
    // 출발 정점으로 부터 가능한 순회 후 1 반환
    return 1;
}

// 깊이 우선 탐색
int dfs(int start)
{
    // 이미 방문한 출발 정점인 경우
    if(visited[start])
        return 0;
    
    // 전형적인 작성 형식
    // 출력없이 방문기록만 남기면 됨
    stack<int> s;
    
    visited[start] = true;
    s.push(start);
    
    while(!s.empty())
    {
        int from = s.top();
        s.pop();
        
        for(int i = 0; i < vertex[from].size(); i++)
        {
            int to = vertex[from][i];
            
            if(!visited[to])
            {
                visited[to] = true;
                s.push(to);
            }
        }
    }
    
    // 방문하지 않은 출발 정점인 경우
    // 출발 정점으로 부터 가능한 순회 후 1 반환
    return 1;
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> N >> M;
    
    // 간선 입력
    for(int m = 0; m < M; m++)
    {
        int a, b;
        cin >> a >> b;
        
        vertex[a].push_back(b);
        vertex[b].push_back(a);
    }
    
    // 모든 정점에서 출발을 시도해봄
    // (방문X 정점 : 1 반환 / 방문O 정점 : 0 반환)
    // BFS 또는 DFS 중 선택
    for(int v = 1; v <= N; v++)
        cnt += bfs(v);
        // cnt += dfs(v);
    
    // 연결 요소의 개수 출력
    cout << cnt;
    
    return 0;
}

 

 

● [백준] - [알고리즘 기초 2/2] - [600 - 그래프 1] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	13023	ABCDE	https://pirateturtle.tistory.com/269
2	1260	DFS와 BFS	https://pirateturtle.tistory.com/270
3	11724	연결 요소의 개수	https://pirateturtle.tistory.com/271
4	1707	이분 그래프	https://pirateturtle.tistory.com/272
5	2667	단지번호붙이기	https://pirateturtle.tistory.com/273
6	4963	섬의 개수	https://pirateturtle.tistory.com/274
7	2178	미로 탐색	https://pirateturtle.tistory.com/275
8	7576	토마토	https://pirateturtle.tistory.com/276
9	7562	나이트의 이동	https://pirateturtle.tistory.com/277