[프로그래머스] 네트워크

---

🔗 문제 링크

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

프로그래머스

---

반응형

728x90

👩‍💻 코드

#include <string>
#include <vector>
#include <iostream>

using namespace std;

void DFS(int v, vector<vector<int>> &computers, vector<bool> &visited){
    if(visited[v]){
        return;
    }
    
    visited[v] = true;
    
    for (int i = 0; i < computers.size(); i++) {
        if (computers[v][i] == 1 && !visited[i]) {
            DFS(i, computers, visited);
        }
    }
}

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

---

📝 풀이

방문을 확인하기 위한 visted를 n만큼 초기화 합니다.

방문하지 않은 경우에만 DFS의 시작점으로 설정한 후 탐색을 시작합니다.

DFS는 연결이 되어 있지만 방문하지 않은 경우에만 재귀적으로 호출하여 연결된 모든 컴퓨터를 방문합니다.

DFS가 실행되는것은 새로운 네트워크가 존재하는 것이므로 answer을 증가시킵니다.

최종적으로 네트워크 개수인 answer를 return 합니다.