[Divide and Conquer 예제] 프로그래머스 Level3 네트워크

문제

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

 

---

문제 풀이 1

네트워크의 개수는 연결되지 않는 컴퓨터들의 상황의 개수이다.

computer[i][i]에서 이동할 수 있는 컴퓨터들을 recursion으로 false로 바꾸어 준다.

 

solution에서, 1~n까지의 컴퓨터 개수대로 dfs를 돌리고,

각 computer[i][i]와 연결되어 있는 컴퓨터들로 이동해서 값을 false로 바꾸어 준다.

만약 마지막이 true로 끝나면 answer++ 한다.

 

#include <string>
#include <vector>

using namespace std;

int answer = 0;
bool dfs(vector<vector<int>>& computers, int iter){
    if(!computers[iter][iter]) return false;
    computers[iter][iter] = 0;
    for(int i = 0;i<computers.size();i++){
        if(computers[iter][i]) dfs(computers, i);
    }
    return true;
}


int solution(int n, vector<vector<int>> computers) {
    for(int i =0;i<n;i++){
        if(computers[i][i] && dfs(computers, i))
        answer++;
    }
    return answer;
}

문제 풀이 2

#include <string>
#include <vector>

using namespace std;

void DFS(int point, vector<vector<int>>& computers, vector<bool>& visit, int n){
    visit[point] = true;
    for (int i = 0; i < n; i++) {
        if (!visit[i] && computers[point][i]) DFS(i, computers, visit, n);
    }
}

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]) {
            answer++;
            DFS(i, computers, visit, n);
        }
    }
    return answer;
}

vector<bool> visit 을 이용해서 방문함을 표시하는 bool 함수 사용한다.

마찬가지로 1~n까지의 컴퓨터개수만큼 반복하는데 i번째 컴퓨터를 방문했는지 검사하고,

방문 못했다면 answer ++해주어 그 컴퓨터와 연결된 컴퓨터를 찾아가서 방문표시를 해주면서 돌아온다.

 

다시 main에서 그다음 컴퓨터 방문을 check할 때 안되어있는 컴퓨터만 검사한다.