알고리즘(c++) / 프로그래머스 level 3 : 네트워크

level 3 :  네트워크

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

코딩테스트 연습 - 네트워크

 

코드

//프로그래머스 네트워크
#include <iostream>
#include <string>
#include <vector>

using namespace std;

vector<vector<int>> computers_copy;
bool visited[201] = { false, };

void DFS(int node) {
    visited[node] = true; //방문한 노드
    for (int i = 0; i < computers_copy.size(); i++) {
        if (visited[i] == false) {
            if (computers_copy[node][i] == 1) {
                DFS(i);
            }
        }
    }

}

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    computers_copy = computers; //전역변수
    for (int i = 0; i < n; i++) {
        if (visited[i] == false) {
            DFS(i);
            answer++;
        }
    }

    return answer;
}

int main() {
    int n = 3;
    vector<vector<int>> computers = { {1,1,0}, {1,1,1}, {0,1,1} };
    cout << solution(n, computers) << "\n";

    return 0;
}

 

설명

computers를 computers_copy로 전역 변수 선언하였다. DFS에서 참조형 변수(&)로 선언할 수 있지만 전역변수로 선언하여 더 편하게 구현할 수 있다. 노드의 방문을 확인하는 visited도 마찬가지로 전역변수로 선언해주었다.

방문되지 않은 노드 중 이동할 수 있는 노드인지를 판단하여 이동하게 된다.(DFS) 

 

고찰

백준에서도 DFS/BFS 문제를 많이 풀어봐서 쉽게 구현할 수 있었던거 같다.