Beakjoon] 연결 요소의 개수 (백준 11724 코테) - 탐색

---

문제주소 : https://www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

문제 

 

풀이

 - 기본적인 DFS 문제로 그래프를 그리고 재귀함수로 풀어내면 됨

 

코드는 아래 숨김

#include <iostream>
#include <vector>

std::vector<std::vector<int>> graph_map;
std::vector<bool> visited;

void DFS(int v) {
    if (visited[v] == true) return;

    visited[v] = true;

    for (int i = 0; i < graph_map[v].size(); ++i) {
        if (visited[graph_map[v][i]] == false) {
            DFS(graph_map[v][i]);
        }
    }
}


int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);

    int n, m;
    std::cin >> n >> m;
 
    graph_map.resize(n + 1);
    visited = std::vector<bool>(n+1, false);

    for (int i = 0; i < m; ++i) {
        int first, second;
        std::cin >> first >> second;
        graph_map[first].push_back(second);
        graph_map[second].push_back(first);
    }

    int count = 0;

    for (int i = 1; i < n+1; ++i) {
        //if (std::find(visited.begin(), visited.end(), false) != visited.end()) {
        if(visited[i] == false){
            ++count;
            DFS(i);
        }
    }

    std::cout << count;
    
}​

 

알게 된 것 :

 - DFS에서 이차원 벡터를 사용하여 그래프를 그리는 법, 이차원 벡터 초기화
 - 방문여부를 별도의 배열에 저장해두는 것
 - 파이썬때는 리스트 슬라이스를 합치는 식으로 했던 거 같기도 한데.. 여튼 이게 더 이해가 쉽다

---