네트워크 - c++ (DFS/BFS)

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

코딩테스트 연습 - 네트워크

문제는 위의 문제이다.

해당 문제는 DFS/BFS의 매우 전형적인 문제중 하나라고 생각이 된다.

 

문제 해결 방법

1. 가장 첫번째 노드에 대하여 DFS/BFS를 실행한다.

2. 각각의 노드들은 방문 됐을때 기록 돼야 한다.

3. DFS/BFS가 끝이나면 네트워크로 형성 되지 못한 노드를 찾아 다시 DFS/BFS를 실행한다.

4. 모든 노드가 방문이 됐다면 DFS/BFS를 실행하지 않는다.

 

=>깊이 혹은 넓이 우선 탐색이 끝나게 되면 하나의 네트워크가 형성이 된것이기에 answer을 하나올려주는 과정이 필요하다.

#include <string>
#include <vector>
#include <queue>

using namespace std;

vector<bool> visit;

void dfs(vector<vector<int>> computers, int where){
	visit[where] = true;//해당 노드를 방문 했음을 표시하는 수단이다.
    
    for(int i=0;i<n;i++){
    	if(visit[i]==true||computers[where][i]==0) continue; //0이라면 해당 노드와 연결이 되어 있지않기 때문에 관계 지을 필요가 없다.
        else dfs(i);//연결된 다음 노드로 넘어가 다시 연결된 노드를 찾게 된다.
    }
}

/*
BFS의 경우 queue를 이용하여야 한다.
생성된 queue에 어떠한 것도 없을때까지 필요한 과정을 반복 하도록 한다.
더불어 visit을 통하여 queue에 이미 들어갔던것들을 표시하는 것도 잊지 말아야 한다.
*/
void bfs(vector<vector<int>> computers, int where){
	visit[where] = true;//해당 노드를 방문 했음을 표시하는 수단이다.
    queue<int> q;
    q.push(where);
    
    while(!q.empty()){
    	int front = q.front();
        q.pop();
        
    	for(int i=0;i<n;i++){
        	if(visit[i]==true||computers[front][i]==0) continue;
            else{
            	visit[i] = true;//해당 노드를 방문 했음을 표시하는 수단이다.
                q.push(i);//해당 노드와 연결된 다른 노드들을 차례차례 넣게 된다.
            }
        }
    }
}

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;

	for(int i=0;i<n;i++){
    	visit.push_back(true);
    }
    
    for(int i=0;i<n;i++){
    	if(visit[i]==false){
        	//dfs(i);
            bfs(i);
            answer++;
        }
    }

	return answer;
}