[c++ 백준 2606 ] 인접리스트, 인접행렬 풀이

인접행렬 풀이

#include <iostream>
#include <vector>
using namespace std;

void dfs(vector<vector<int>> &v, const int N, const int node, vector<int> &visited){
    if (!visited[node]) visited[node] = 1;
    else return;
    for (int i = 1; i < N+1; ++i)
        if (v[node][i]) 
            dfs(v, N, i, visited);
}

int main(int argc, char **argv){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
        
    int N, M, s, e;
    cin >> N >> M;
    
    vector<int> visited(N+1);
    vector<vector<int>> v(N+1, vector<int>(N+1,0)); // 인접행렬
    for (int i = 0 ; i < M; ++i){
        cin >> s >> e;
        v[s][e] = 1;
        v[e][s] = 1;
    }
    
    dfs(v, N, 1, visited);
    
    int cnt = 0;
    for (int i = 0; i < N+1; ++i){
        if (visited[i]) ++cnt;
    }
    cout << cnt-1;
    return 0;
}

 

인접리스트 풀이

#include <iostream>
#include <vector>
using namespace std;

void dfs(vector<int> v[], const int N, const int node, vector<int> &visited){
    if (!visited[node]) visited[node] = 1;
    else return;
    for (int i: v[node])
        dfs(v, N, i, visited);
}

int main(int argc, char **argv){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
        
    int N, M, s, e;
    cin >> N >> M;
    
    vector<int> visited(N+1);
    vector<int> v[N+1]; // 인접리스트
    for (int i = 0 ; i < M; ++i){
        cin >> s >> e;
        v[s].push_back(e);
        v[e].push_back(s);
    }
    
    dfs(v, N, 1, visited);
    
    int cnt = 0;
    for (int i = 0; i < N+1; ++i){
        if (visited[i]) ++cnt;
    }
    cout << cnt-1;
    return 0;
}

 

- vector는 주소가 아닌 '깊은복사'되어 값으로 전달되기 때문에 &를 사용해서 주소로 전달해준다. (전역변수로 선언한다면 신경안써도 되므로 좀 더 편하긴 하다. 연습삼아 저렇게 코딩한다.)