프로그래머스 Level3 - 네트워크 C++

주어진 컴퓨터가 연결되어 있는 만큼 네트워크의 수를 구하는 문제.

지인짜 간단한 문제 같지만 백준에서만 풀어봐서 그런지 익숙하지가 않았다

백준에서는 그냥 전역변수로 선언하는 식으로 했었는데

이건 함수로 주어지니까 얘를....전역으로 복사를 해야되나..했는데 그러기엔 너무 비효율적이고..

걍 포인터를 쓰면 될 일이었음..^^

 

 

 

풀이)

visit vector를 두고, n만큼 반복해주면 된다

 

#include <string>
#include <vector>
 
using namespace std;
 
void dfs(vector<bool>& visit, vector<vector<int>>& computers, int n, int v){
    visit[v] = true;
    
    for(int i=0;i<n;i++){
        if(!visit[i] && computers[v][i]){
            dfs(visit,computers,n,i);
        }
    }
}
 
 
int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    
    vector<bool> visit(n,false);
    
    for(int i=0;i<n;i++){
        if(!visit[i]){
            dfs(visit,computers,n,i);
            answer++;
        }
    }
    
    return answer;
}

 

 

 

 

이걸 풀고 나서 다른 더 효율적인 방법이 없을까 했는데

https://mungto.tistory.com/52

이렇게 푸는 방법도 있었다.

컴퓨터를 하나씩 삭제하는 방식!

computers[i][i]가 항상 1이라는걸 이용했다고하는데, 이렇게하면 visit배열도 필요 없다.

 

#include <string>
#include <vector>
 
using namespace std;
 
bool dfs(vector<vector<int>>& computers, int v){
    //이미 방문했고, 그래서 삭제된 컴퓨터라면 반환
    if(!computers[v][v]) return false;
    
    //컴퓨터 삭제
    computers[v][v]=0;
    
    for(int i=0;i<computers.size();i++){
 
        //연결된 컴퓨터중에 아직 지우지 않은 컴퓨터라면 방문해서 삭제
        if(computers[v][i]) {
            dfs(computers,i);
        }
                                       
    }
    return true;
}
 
 
int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    
    for(int i=0;i<n;i++){
        //아직 방문하지 않으면 dfs 돌고 나와서 answer++
        if(computers[i][i] && dfs(computers,i))
            answer++;
    }
    
    return answer;
}