[프로그래머스] 네트워크 (깊이/너비 우선 탐색(DFS/BFS), C++)

📝 문제풀이 과정

---

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

void BFS(int start, vector<int> *graph, bool *visited){
    queue<int> q;
    visited[start] = true;
    q.push(start);
    printf("%d visited.\n", start);

    while(!q.empty()){
        int current = q.front();
        q.pop();
        for(int next: graph[current]){
            if(visited[next] == false){
                visited[next] = true;
                q.push(next);
                printf("%d visited.\n", next);
            }
        }
    }

}
int solution(int n, vector<vector<int>> computers){
    vector<int> graph[n];
    bool visited[n];
    int cnt=0;
    fill(visited, visited+n, false);

    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(computers[i][j] == 1){
                graph[i].push_back(j);
            }
        }
    }
    
    
    for(int i=0; i<n; i++){
        if(visited[i] == false) { 
            BFS(i, graph, visited); 
            cnt++; printf("%d\n", cnt);
        }
    }
    
    return cnt;
}

int main(){
    int n; // n: # of computers
    scanf("%d", &n);
    vector<vector<int>> computers;

    for(int i=0; i<n; i++){
        vector<int> v;
        for(int j=0; j<n; j++){
            int num; scanf("%d", &num);
            v.push_back(num);
        }
        computers.push_back(v);
    }

    printf("%d\n", solution(n, computers));
}

computers에서 computers[i][j] == 1인 경우에만 vector에서 graph[i]에 j를 넣어줬다.

그럼 다음과 같이 연결성을 나타낼 수 있다.

 

BFS로 탐색을 진행해서 연결성이 있는 경우 BFS 함수 내에서 start 정점에 대해 연결된 모든 정점에 대해 방문을 하고 큐가 비면 탐색을 끝내고 리턴한다. 이것을 하나의 연결성으로 간주하고 main으로 리턴 후 카운팅을 증가시키면 된다.

위와 같이 한번 연결된 정점들 방문을 끝내면 cnt를 증가하고 출력하는 과정으로 제대로 방문하는지 확인해봤다.

 

void DFS(int start, vector<int> *graph, bool *visited){
    visited[start] = true;

    for(int next: graph[start]){
        if(!visited[next]) DFS(next, graph, visited);
    }
}

DFS의 경우, 재귀 호출로 구현해봤고, BFS 함수를 DFS 함수로 바꿔주기만 하면 된다.

 

 

💻 C++ 제출코드

---

#include <string>
#include <vector>
#include <queue>
using namespace std;

void BFS(int start, vector<int> *graph, bool *visited){
    queue<int> q;
    visited[start] = true;
    q.push(start);

    while(!q.empty()){
        int current = q.front();
        q.pop();
        for(int next: graph[current]){
            if(visited[next] == false){
                visited[next] = true;
                q.push(next);
            }
        }
    }

}

int solution(int n, vector<vector<int>> computers){
    vector<int> graph[n];
    bool visited[n];
    int cnt=0;
    fill(visited, visited+n, false);

    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(computers[i][j] == 1){
                graph[i].push_back(j);
            }
        }
    }
    
    
    for(int i=0; i<n; i++){
        if(visited[i] == false) { 
            BFS(i, graph, visited); 
            cnt++; printf("%d\n", cnt);
        }
    }
    
    return cnt;
}

#include <string>
#include <vector>
#include <queue>
using namespace std;

void DFS(int start, vector<int> *graph, bool *visited){
    visited[start] = true;

    for(int next: graph[start]){
        if(!visited[next]) DFS(next, graph, visited);
    }
}

int solution(int n, vector<vector<int>> computers){
    vector<int> graph[n];
    bool visited[n];
    int cnt=0;
    fill(visited, visited+n, false);

    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(computers[i][j] == 1){
                graph[i].push_back(j);
            }
        }
    }
    
    
    for(int i=0; i<n; i++){
        if(visited[i] == false) { 
            //BFS(i, graph, visited); 
            DFS(i, graph, visited);
            cnt++; printf("%d\n", cnt);
        }
    }
    
    return cnt;
}

 

 

👏 결과

---

BFS 채점 결과

DFS 채점 결과