네트워크

💪네트워크 (프로그래머스)

사용언어 : C++
DFS 사용시 매우 유리한 문제
첫 풀이 : 69.2점

---

1. 정답풀이(DFS)

#include <string>
#include <vector>

using namespace std;

vector<int> graph[201];
vector<int> check(201, -1);

void dfs(int start){
    check[start] = 1;
    
    for(int next: graph[start]){
        if (check[next] != 1){
            dfs(next);
        }
    }
    
}

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    
    
    for(int i=0; i<computers.size(); i++){
        for(int j=0; j<computers.size(); j++){
            if(computers[i][j] == 1){
                graph[i].push_back(j);
                //graph[j].push_back(i);
            }
        }
    }
    
    for(int i=0; i<n; i++){
        if(check[i] != 1){
            dfs(i);
            answer++;
        }
    }
    
    
    return answer;
}

---

2. 정답풀이 (BFS)

• 큐가 empty여서 탐색이 끝나도 기존에 방문 안한 노드를 체크해줄 for문 필요하다

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

using namespace std;
int comVisit[201];

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

    for(int v=0; v<n; v++){
    	if(comVisit[v]==0) { 
        //정점 체크, 해당 정점을 방문하지 않았다면 큐에 넣어 순회
        //이전 네트워크 순회 중 방문한 정점은 제외 (큐에 push X)
        
        	cnt++;  
          //이전까지 순회 중 방문하지 않은 정점은 이전 네트워크에 포함되지 않기 때문에
          //새로운 네트워크의 등장으로 보고, cnt+1
         
        	comVisit[v]=cnt; //어떤 네트워크에 속하는지 보기위함. true,false로 체크해도됨
        	q.push(v);   
    	} 

        while(!q.empty()){
        	int check=q.front();
          	q.pop();

          	for(int i=0; i<n; i++){
              	if(computers[check][i]!=0 && i!=check){
                //check하는 정점과 연결된 애들 중 방문하지 않은 정점은 방문체크 후 큐에 푸시
                 	if(comVisit[i]==0) {
                      	comVisit[i]=cnt;
                      	q.push(i);
                  	}
              	}
          	}
    	}
    }
    
    return cnt;
}

---

3. 첫 풀이

단방향일때 테스트 케이스 통과 안됨

#include <iostream>
#include <string>
#include <vector>
#include <deque>

using namespace std;

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    int max = computers[0].size();
    vector<int> graph[200];
    int dist[200];
    
    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++){
        dist[i] = -1;
    }
  
    deque<int> q;
    q.push_back(0);
        
    dist[0] = 0;
    
    while(!q.empty()){
        int now = q.front();
        q.pop_front();
        
        for(int next : graph[now]){
            if(dist[next] == -1){
                dist[next] = dist[now] + 1;
                q.push_back(next);
                answer++;
            }
        }
 
    }
    return n-answer;
 
}

4. 링크

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