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

DFS를 이용하는 문제이다. 그 중에서도, 그래프의 모든 노드가 연결되어 있지 않은 경우를 해결하는 문제이다. 모든 노드를 방문하기 위해서 solution()에서 for문을 사용하여 DFS를 호출해야한다. 

 

---

1. Solution 코드

#include <string>
#include <vector>

using namespace std;

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

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    vector<bool> visit(n, false);
    
    for(int j = 0; j < n; j++){
        if(!visit[j]){
            answer++;
            DFS(n, computers, j, visit);
        }
    }
    
    return answer;
}

2. 알아야 할 개념

1) Call by Reference 와 Call by Value

함수를 호출하는 방법은 2가지가 있다. Call by Reference(참조에 의한 호출)은 인자로 받은 값의 주소를 참조하여 직접 값에 영향을 준다. (직접 참조) 즉, 별명을 통하여 변수의 메모리 공간에 직접 접근하는 방법이다. Call by Value(값에 의한 호출)은 인자로 받은 값을 복사하여 처리한다.

 

"네트워크" 문제를 해결하기 위해서는 DFS() 함수의 인자인 visit을 Call by Reference 해야만 한다. 왜냐하면, vector<bool> visit 의 갱신된 값을 solution() 의 DFS()에서 계속 이용하기 때문에, DFS()에서 갱신된 vector visit을 solution으로 전달해야만 한다. 따라서, 갱신된 값 전달이 안 되는 Call by Value가 아니라, 갱신된 값을 전달할 수 있는 Call by Reference를 이용한다.

 

 

 

 

 

#프로그래머스 #C++ #네트워크 #DFS