[BaekJoon 11724번] 연결 요소의 개수(C++)

※주의※

저의 풀이가 정답은 아닙니다.

다른 코드가 더 효율적이거나 좋을 수 있습니다.

언제나 다른 사람의 코드는 참고만 하시기 바랍니다.

 

 

[문제 풀이 사이트]

 

 

11724번: 연결 요소의 개수

 

 

[문제 설명]

 

 

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

 

 

[입력]

 

 

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

 

 

[출력]

 

 

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

 

 

[입출력 예]

 

 

입력	출력
6 5 1 2 2 5 5 1 3 4 4 6	2
6 8 1 2 2 5 5 1 3 4 4 6 5 4 2 4 2 3	1

 

 

[문제 풀이]

 

해당 문제는 재귀 DFS, 비재귀 DFS, BFS 총 3가지의 방법으로 풀어보았다.

 

이 문제와 같이 정점과 간선이 주어졌을 때 인접리스트를 만들어야 한다.

 

문제에서는 방향성이 없는 그래프라고 주어졌기 때문에 무방향 그래프를 만들어보도록 하겠다.

인접리스트를 만들 땐 vector를 이용한다!

 

1. 정점의 개수 + 1만큼 vector를 생성한다.(정점은 0부터 시작하지 않아서 +1 함)

vector<int> adj_matrix[정점 개수 + 1];

 

2. 무방향 그래프는 간선의 양 끝점의 입력을 받을 때 다음과 같이 코드를 작성한다.

adj_matrix[시작 정점].push_back(도착 정점);

adj_matrix[도착 정점].push_back(시작 정점);

 

(만약 방향 그래프 문제가 나온다면 한방향으로만 구현하면 된다.)

ex) adj_matrix[시작 정점].push_back(도착 정점);

 

그래서 입출력 예를 보면

6개의 정점과 5개의 간선의 개수가 주어지고, 간선의 개수에 따른 간선의 양 끝점을 입력받는다.

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

 

그렇다면 인접 리스트를 만들기 위해 코드를 아래와 같이 작성한다.

for (int i = 1; i <= M; ++i) {
        int u, v;
        cin >> u >> v;
        // 무방향 그래프
        adj_matrix[u].emplace_back(v);
        adj_matrix[v].emplace_back(u);
}

 

adj_matrix[시작 정점].emplace_back(도착 정점);

adj_matrix[도착 정점].emplace_back(시작 정점);

 

adj_matrix[시작 정점].emplace_back(도착 정점)의 형식인데

시작 정점으로부터 도착 정점까지 이어진 간선이 존재한다는 뜻이다.

 

입출력예1 인접 리스트

입출력 예1 인접 리스트 vector

그래서 입출력 예처럼 간선의 양 끝점(시작 정점, 도착 정점)을 입력하고나면 위와 같은 인접리스트가 형성이 된다.

그리고 생성한 인접리스트 vector는  또한 위와 같은 형태를 보여준다.

 

 

이제 인접 리스트가 형성이 됬으니 연결 요소의 개수를 구하기 위해 재귀 DFS를 이용하여 설명해보도록 하겠다.

(재귀 DFS, 비재귀 DFS, BFS로도 풀 수 있지만, 내가 취약한 부분인 재귀 DFS를 설명!)

 

 

1. 우선 방문 여부를 체크하기 위한 boolean 배열을 만들어야한다.

해당 배열은 정점의 개수 + 1만큼 크기로 만들면 된다.(하지만 문제에선 범위가 1 ~ 1000까지이기 때문에 전역으로 해당 크기만큼 배열을 생성한 점 참고)

 

2.  for문을 이용하여 정점의 개수만큼 각 정점을 확인한다.

int num = 0;
for(int i = 1; i <= N; ++i) {
        if(visited[i]) continue;
        dfs(i);
        num += 1;
}

 

3. for문을 통해 먼저 1번 정점을 방문했는지 확인한다.방문하지 않았다면 dfs(1)을 넘겨준다.

 

void dfs(int cur) {
    visited[cur] = true;
    for(auto nxt : adj_matrix[cur]) {
        if(visited[nxt]) continue;
        dfs(nxt);
    }
}

넘겨주게 되면 visited[cur] = true를 통해 해당 정점(1)을 방문 했다고 표시를 한다.

 

그리고 cur로 전달된 정점(1)과 연결된 정점들을 순회(확인)한다.

정점들을 순회(확인)하면서 연결된 정점이(nxt) 이미 방문한 정점인지 확인한다.

방문하지 않은 정점이라면 dfs 함수를 재귀적으로 호출한다.

 

4. 그렇다면 1과 연결된 다음 정점이 2이기 때문에 dfs(2)를 호출한다.

visited[2] = true를 통해 해당 정점(2)를 방문했다고 표시를 한다.

 

2와 연결된 정점들을 순회(확인)한다.

2와 연결된 정점 중 1은 이미 방문한 정점이기 때문에 dfs를 호출하지 않고 넘어간다.

그리고 다음 연결된 정점 5를 확인한다. 5는 방문한 적이 없기 때문에 dfs(5)를 호출한다.

 

5. visited[5] = true를 통해 정점(5)를 방문했다고 표시를 한다.

5와 연결된 정점들을 순회(확인)한다.

1의 경우 이미 방문했기 때문에 dfs를 호출하지 않고, 2의 경우 또한 이미 방문했기 때문에 dfs를 호출하지 않는다.

연결된 모든 정점을 확인했기 때문에 반복문을 종료하고

이전 for문에서 정점 1을 호출했던 부분으로 돌아가게 된다. (2번 부분)

 

여기까지 진행한 정점들은 아래와 같은 상태이다.

(빨간색 정점이 방문한 정점, 파란색 정점이 아직 방문하지 않은 정점)

 

 

다시 시작 정점을 찾기 위해 정점1을 호출했던 for문으로 다시 되돌아가보자.

int num = 0;
for(int i = 1; i <= N; ++i) {
        if(visited[i]) continue;
        dfs(i);
        num += 1;
}

정점이 1과 연결된 정점들을 다 탐색했으므로 +1을 해준다. (연결 요소 + 1)

 

그리고 for문을 통해 2번 정점을 방문했는지 확인한다. 방문했으므로 패스

3번 정점을 방문했는지 확인한다. 방문하지 않았으므로 위 과정과 같이 3번을 방문했다고 표시를 한다.

그리고 3번 정점과 연결된 정점들을 순회(확인)한다.

 

연결된 4번 정점은 방문하지 않았으므로 dfs(4)를 호출한다.

4번을 방문 표시한다. 4번과 연결된 정점들을 순회(확인)한다.

 

4번과 연결된 정점 6는 방문하지 않았으므로 dfs(6)을 호출한다.

6번을 방문 표시하고 6번과 연결된 정점들을 순회(확인)한다. 연결된 정점이 없기 때문에 DFS를 종료한다.

 

다시 4번 정점으로 돌아와서 4번과 연결된 모든 정점을 방문했기 때문에  DFS를 종료한다.

다시 3번 정점으로 돌아와서 3번과 연결된 모든 정점을 방문했기 때문에 DFS를 종료한다.

그리고 정점이 3과 연결된 정점들을 다 탐색했으므로 +1을 해준다. (연결 요소 + 1)

 

그리고 정점이 4, 5, 6 들을 확인하면서 방문했으므로 패스하고 반복문을 종료한다.

 

그래서 연결 요소는 2개로 정답을 구할 수 있었다.

 

 

[최종 코드]

 

 

[GitHub]

 

 

(비재귀 DFS 풀이)

GitHub - SmallPeanutPark/BAEKJOON: Study BaekJoon for Coding Test

 

(재귀 DFS 풀이)

GitHub - SmallPeanutPark/BAEKJOON: Study BaekJoon for Coding Test

 

(BFS 풀이)

GitHub - SmallPeanutPark/BAEKJOON: Study BaekJoon for Coding Test

 

(비재귀 DFS 풀이)

#include <bits/stdc++.h>
using namespace std;

bool visited[1001];
vector<int> adj_matrix[1001];

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M; // 정점의 개수 간선의 개수 M
    cin >> N >> M;
    fill(visited, visited + 1001, false);
    
    for (int i = 1; i <= M; ++i) {
        int u, v;
        cin >> u >> v;
        // 무방향 그래프
        adj_matrix[u].emplace_back(v);
        adj_matrix[v].emplace_back(u);
    }

    // 비재귀 dfs
    stack<int> st;
    int num = 0;
    for (int i = 1; i <= N; ++i) {
        if (visited[i]) continue;
        num += 1;
        st.push(i);
        visited[i] = true;
        while (!st.empty()) {
            int cur = st.top();
            st.pop();
            for (auto element : adj_matrix[cur]) {
                if (visited[element]) continue;
                st.push(element);
                visited[element] = true;
            }
        }
    }
    cout << num;
}

 

(재귀 DFS 풀이)

#include <bits/stdc++.h>
using namespace std;

bool visited[1001];
vector<int> adj_matrix[1001];

void dfs(int cur) {
    visited[cur] = true;
    for(auto nxt : adj_matrix[cur]) {
        if(visited[nxt]) continue;
        dfs(nxt);
    }
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M; // 정점의 개수 간선의 개수 M
    cin >> N >> M;
    fill(visited, visited + 1001, false);
    
    for (int i = 1; i <= M; ++i) {
        int u, v;
        cin >> u >> v;
        // 무방향 그래프
        adj_matrix[u].emplace_back(v);
        adj_matrix[v].emplace_back(u);
    }

    // 재귀 dfs
    int num = 0;
    for(int i = 1; i <= N; ++i) {
        if(visited[i]) continue;
        dfs(i);
        num += 1;
    }
    cout << num;
}

 

(BFS 풀이)

#include <bits/stdc++.h>
using namespace std;

bool visited[1001];
vector<int> adj_matrix[1001];

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M; // 정점의 개수 간선의 개수 M
    cin >> N >> M;
    fill(visited, visited + 1001, false);
    
    for (int i = 1; i <= M; ++i) {
        int u, v;
        cin >> u >> v;
        // 무방향 그래프
        adj_matrix[u].emplace_back(v);
        adj_matrix[v].emplace_back(u);
    }

    // bfs
    queue<int> q;
    int num = 0;
    for (int i = 1; i <= N; ++i) {
        if (visited[i]) continue;
        num += 1;
        q.push(i);
        visited[i] = true;
        while (!q.empty()) {
            int cur = q.front();
            q.pop();
            for(int j = 0; j < adj_matrix[cur].size(); ++j) {
                if(visited[adj_matrix[cur][j]]) continue;
                q.push(adj_matrix[cur][j]);
                visited[adj_matrix[cur][j]] = true;
            }
        }
    }
    cout << num;
}