[programmers] Lv.3 네트워크(c++)

DFS에 대한 두려움이 많이 줄어든것같다.

 

#include <string>
#include <vector>

using namespace std;

void dfs(vector<vector<int>>& computers, int i){
    computers[i][i] = 0;
    
    for(int k=0; k<computers.size(); k++){
        if(computers[i][k] == 1 && computers[k][k] == 1) dfs(computers, k);
    }
}

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

---

문제

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

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

728x90

---

[접근]

DFS

https://jolly-note.tistory.com/62?category=993245 

DFS (Depth First Search, 깊이 우선 탐색)

---

[접근1]

컴퓨터에 방문한 여부는 computers[i][i]를 보면 알 수 있다.

따라서 0부터 n-1까지 돌면서 computers[i][i]가 1이면 dfs로 들어간다.

하나의 네트워크를 전부 돌고 나올것이기 때문에, answer를 1 증가시켜준다.

for(int i=0; i<n; i++){
    if(computers[i][i] == 1) {
        dfs(computers, i);
        answer++;
    }
}

---

[접근2] - dfs함수 내부

현재 컴퓨터의 방문 여부를 나타내기 위해 computers[i][i]를 0으로 만든다.

그리고 연결돼있는 컴퓨터들을 알기 위해서 0부터 computers.size()까지 돌면서('다른사람풀이'에서 computers.size()를 바깥으로 빼주라고한다.) 만약 연결되어있고, 연결돼있는 컴퓨터가 아직 방문 전이라면  dfs로 들어간다.

void dfs(vector<vector<int>>& computers, int i){
    computers[i][i] = 0;
    
    for(int k=0; k<computers.size(); k++){
        if(computers[i][k] == 1 && computers[k][k] == 1) dfs(computers, k);
    }
}