[백준(BOJ)] 11724번 : 연결 요소의 개수 - C++[CPP]

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

11724번: 연결 요소의 개수

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

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

 

---

 

⊙ 문제 접근 과정

 

BFS로 접근하여 문제를 풀었다.

 

1. 값을 입력받으면 대칭적으로 '1' 값 저장

2. 1부터 시작, queue에 '1' 값 넣고 방문 표시, 반복

3. N까지 반복하는데 방문을 안 했다면 count up 후, bfs 실행

2. 모두 방문했다면 count 출력

 

위 로직과 같이 풀었다.

---

 

⊙ 문제 풀이

 

#include <iostream>
#include <queue>

using namespace std;
#define MAX 1001

int N,M,cnt=0;

int arr[MAX][MAX];
bool visited[MAX];
queue<int> q;

void bfs(int k) {
    q.push(k);
    visited[k]=true;
    cnt++;

    while(!q.empty()) {
        k = q.front();
        q.pop();

        for(auto i =1;i<=N;i++) {
            if(arr[k][i]==1 && !visited[i]) {
                q.push(i);
                visited[i]=true;
            }
        }
    }
}

int main() {
    cin >> N>>M;

    for(auto i=1;i<=M;i++) {
        int u,v;
        cin >> u >> v;
        arr[u][v]=1;
        arr[v][u]=1;
    }
    
    for(auto i=1;i<=N;i++) {
        if(!visited[i]) {
            bfs(i);
        }
    }

    cout << cnt;
}

 

---

⊙ 결과

 

---

⊙ 마무리

 

 

NONE

 

좋아요는 로그인하지 않아도 누를 수 있습니다!