[프로그래머스 / C++] 네트워크

https://programmers.co.kr/learn/courses/30/lessons/43162

문제 풀이

백준 연결요소의 개수 문제랑 똑같은 문제이다! DFS, BFS둘 다 이용해서 풀 수 있다. 연결요소 입력 받는 형태를 복습하기 위해 글을 또 써본다..👀 +) visited랑 dfs, bfs 쓰는 방법은 하던 거랑 똑같다

벡터 배열 이용해서 입력 받기

vector<int> map[MAX];

for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(i==j) continue;
            
            if(computers[i][j]==1){
                map[i].push_back(j);
                map[j].push_back(i);
            }
        }
    }

코드

#include <string>
#include <vector>
#include <queue>
#define MAX 201

using namespace std;
vector<int> map[MAX];
bool visited[MAX];
int answer = 0;

void dfs(int start){
    for(int i=0;i<map[start].size();i++){
        if(!visited[map[start][i]]){
            visited[map[start][i]]=true;
            dfs(map[start][i]);
        }
    }
}

void bfs(int start){
    queue<int> q;
    q.push(start);
    
    while(!q.empty()){
        int cur=q.front();
        q.pop();
        
        for(int i=0;i<map[cur].size();i++){
            if(!visited[map[cur][i]]){
                visited[map[cur][i]]=true;
                bfs(map[cur][i]);
            }
        }
    }
}


int solution(int n, vector<vector<int>> computers) {
    
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(i==j) continue;
            
            if(computers[i][j]==1){
                map[i].push_back(j);
                map[j].push_back(i);
            }
        }
    }
    
   	// 모든 컴퓨터들을 검사 
    for(int i=0;i<n;i++){
        if(!visited[i]){ 
            visited[i]=true;
           	//dfs(i);
            bfs(i);
            answer++;
        }
    }

    return answer;
}