네트워크

문제 링크

네트워크의 개수를 구하는 문제인데, connected_component 의 개수를 구하는 문제이다.

그래프의 연결된 노드들을 따라서 탐색하다가 연결이 끊기면 네트워크 하나가 끝난 것이므로 +1 해주며 네트워크의 개수를 구하면 된다고 풀이법을 생각할 수 있다.

방법 1 : DFS

#include <vector>

using namespace std;
int visited[204];

void dfs(int current_computer, int n, vector<vector<int>>& computers){
    // visited에 current_computer번째 컴퓨터를 방문했다고 표시하기
    visited[current_computer] = 1;
    
    for(int i=0; i<n; i++){
        // current_computer와 연결된 컴퓨터들 탐색 시작
        if(visited[i] == 0 && computers[current_computer][i] == 1){
            dfs(i, n, computers);
        }
    }
}

// 컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers 
int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    
    for(int i = 0; i < n; i++){
        //아직 검사하지 않은 컴퓨터일때 탐색 시작
        if(visited[i] == 0){
            dfs(i, n, computers);
            
            // 재귀적으로 호출한 dfs함수가 여기로 돌아올 때가 connected component (연결된 그래프) 하나이므로 +1을 해준다
            answer++;
        }
    }
    return answer;
}

방법 2 : BFS

#include <vector>
#include <queue>

using namespace std;

void bfs(int start, vector<vector<int>>& computers, vector<bool>& visited) {
    queue<int> q;
    q.push(start); // 시작 노드를 큐에 넣는다
    visited[start] = true; // 시작 노드를 방문했음을 표시한다

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

        for (int i = 0; i < computers.size(); i++) {
            if (computers[cur][i] && !visited[i]) {
                q.push(i);
                visited[i] = true;
            }
        }
    }
}

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    vector<bool> visited(n, false); // 방문 여부를 나타내는 벡터의 모든 요소를 false로 초기화하여, 초기에는 아무 노드도 방문하지 않았다고 가정한다

    for (int i = 0; i < n; i++) {
        if (!visited[i]) { 
            bfs(i, computers, visited);
            answer++;
        }
    }

    return answer;
}

---

타겟 넘버

문제 링크

입력된 수들로 더하기 또는 빼기를 반복하여 만들 수 있는 경우의 수는 각각 수별로 +, - 를 하는 방법 2가지이므로 2^5(=32)가지이다.

매개변수만 다르고 로직이 같다면 재귀방식을 생각해 볼 수 있다.

무한루프에 빠지지 않도록 재귀함수의 종료조건을 먼저 정의해야한다.

• 탐색 시, numbers벡터의 모든 원소를 사용하였으면 return해야 한다.
  numbers.size()와 numbers 벡터의 인덱스를 가리키고 있는 index변수의 값이 같으면 numbers벡터의 모든 원소를 사용했다는 뜻.
• 또한 모든 원소를 사용하였으며 그때의 합이 타겟넘버와 같으면 전역변수 answer에 1을 더해준다.

#include <string>
#include <vector>

using namespace std;

// 타겟 넘버를 만드는 방법의 수 (전역변수로 가지고 나왔다)
int answer = 0;
    
// vector를 넘겨줄때 레퍼런스로 넘겨줘야한다. copy하면서 시간복잡도가 O(N)으로 늘어나기 때문

void dfs(vector<int> &numbers, int &target, int sum, int index){
    // 종료 조건
    if(index == numbers.size()){
        if(sum == target){
            answer++;
        }
        // 같지 않을 때도 return
        return;
    }
    // 종료 조건이 만족되지않으면 계속 탐색
    dfs(numbers, target, sum + numbers[index], index + 1);
    dfs(numbers, target, sum - numbers[index], index + 1);
}

// 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target
int solution(vector<int> numbers, int target) {
    dfs(numbers, target, 0, 0);
    return answer;
}