[프로그래머스] 네트워크 C++ (Lv.3)

 

 

 

 

 

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

프로그래머스

 

이번 문제는 DFS 문제였습니다.

 

 

 

 

 

 

📝 문제 풀이

1. 0 컴퓨터를 시작으로 i 컴퓨터와 직간접적으로 연결된 모든 컴퓨터(computers[i])를 탐색

2.  i 컴퓨터와 직간접적으로 연결된 컴퓨터는 방문 표시 visited[i] = true

3. DFS 함수가 종료되면 answer += 1 (하나의 네트워크임을 표현)

 

 

 

 

👩🏻‍💻 C++ 코드

#include <string>
#include <vector>
#define MAX 200

using namespace std;

bool visited[MAX];

void DFS(int i, int n, vector<int> &computer, vector<vector<int>> &computers) {
    visited[i] = true;
    
    for (int i=0; i<n; i++) {
       if (visited[i] || computer[i] == 0) continue;
        
        DFS(i, n, computers[i], computers);
    }
}

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

 

 

프로그래머스 - 결과 화면