[프로그래머스] 네트워크 / DFS, BFS 그래프 탐색 / C++ 풀이

문제 링크

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

프로그래머스

 

풀이 전략

주어진 벡터 computers는 인접 행렬로 두 컴퓨터 간의 연결 상태를 표현한다. 각 컴퓨터를 노드로 하여 방문하지 않은 노드에 대해 그래프 탐색을 수행한다. 서로 연결된 노드를 탐색해가며 방문했음을 표시한다. 한 번의 그래프 탐색 호출 시 서로 연결된 모든 노드를 탐색하게 되므로 하나의 네트워크를 찾게 된다. 따라서 그래프 탐색을 호출한 횟수가 네트워크의 수 이다.

 

C++ 코드

/*
https://school.programmers.co.kr/learn/courses/30/lessons/43162
*/
#include <vector>

using namespace std;
int A[200][200]; //인접 행렬
int V[200]; //방문 리스트
int N;

void DFS(const int cur) {
    for(int next = 0; next < N; ++next) {
        if(cur == next || A[cur][next] == 0 || V[next]) {continue;}
        V[next] = true;
        DFS(next);
    }
}

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    N = n;
    for(int i = 0; i < N; ++i) {
        V[i] = false;
    }
    
    for(int i = 0; i < N; ++i) {
        for(int j = 0; j < N; ++j) {
            A[i][j] = computers[i][j];
        }
    }
    
    for(int i = 0; i < N; ++i) {
        if(V[i] == false) {
            V[i] = true;
            DFS(i);
            answer++;
        }
    }
    
    return answer;
}