11724번: 연결 요소의 개수

문제링크

C++(BFS)

#include <iostream>
#include <vector>
#include <utility>
#include <queue>

using namespace std;

unsigned short N;
unsigned int M;
unsigned short u, v;

vector<short> adj_lst[1001];

char    visited[1001];

queue <int> Q;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M;
    for (int i = 0; i < M; i++){
        cin >> u >> v;
        adj_lst[u].push_back(v);
        adj_lst[v].push_back(u);
    }

    int ret = 0;
    for (int t = 1; t <= N; t++){
        if (visited[t] == 0){
            ret++;
            Q.push(t);
            visited[t] = 1;
            while (!Q.empty()){
                int tmp = Q.front();
                Q.pop();
                for (auto &i : adj_lst[tmp]){
                    if (visited[i] == 0){
                        Q.push(i);
                        visited[i] = 1;
                    }
                }
            }
        }
    }
    cout << ret << "\n";

}

C++(DFS 재귀)

#include <iostream>
#include <vector>
#include <utility>

using namespace std;

unsigned short N;
unsigned int M;
unsigned short u, v;

vector<short> adj_lst[1001];

char    visited[1001];

void dfs(int nod){
    if (visited[nod] == 1){
        return ;
    }
    visited[nod] = 1;
    for (auto &i : adj_lst[nod]){
        if (visited[i] == 0){
            dfs(i);
        }
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M;
    for (int i = 0; i < M; i++){
        cin >> u >> v;
        adj_lst[u].push_back(v);
        adj_lst[v].push_back(u);
    }

    int ret = 0;
    for (int t = 1; t <= N; t++){
        if (visited[t] == 0){
            ret++;
            dfs(t);
        }
    }

    cout << ret << "\n";

}

C++(DFS 스택)

#include <iostream>
#include <vector>
#include <utility>
#include <stack>

using namespace std;

unsigned short N;
unsigned int M;
unsigned short u, v;

vector<short> adj_lst[1001];

char    visited[1001];

stack <int> S;

void dfs(int nod){    
    if (visited[nod] == 1)
        return ;
    visited[nod] = 1;
    S.push(nod);
    while (!S.empty()){
        int tmp = S.top();
        S.pop();
        for (auto &i : adj_lst[tmp]){
            if (visited[i] == 0){
                S.push(tmp);
                S.push(i);
                visited[i] = 1;
                break ;
            }
        }
    }

}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M;
    for (int i = 0; i < M; i++){
        cin >> u >> v;
        adj_lst[u].push_back(v);
        adj_lst[v].push_back(u);
    }

    int ret = 0;
    for (int t = 1; t <= N; t++){
        if (visited[t] == 0){
            ret++;
            dfs(t);
        }
    }

    cout << ret << "\n";

}

• BFS로 풀 때 방문 여부 체크를 잘못해서 계속 메모리 초과 발생.
  • 큐에 노드 넣는 순간 방문 체크해주지 않으면 다른 노드에서 인접리스트를 확인할 때 아직 방문하지 않았다고 생각해서 다시 큐에 넣는 문제가 발생한다. -> 오류 및 메모리 초과
  • 따라서 큐에 노드를 넣는 순간 방문 체크를 해주어야 한다.
• BFS/DFS 모두 인접 리스트로 푸는 경우 $O(V + E)$ , 인접 행렬로 푸는 경우 $O(V^{2})$