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

 

 

문제

소스코드

 

 

#include <vector>
#include<queue>
#include<algorithm>
using namespace std;
 
constexpr int MAX_COMPUTERS = 201;
 
bool g_visited[MAX_COMPUTERS];
 
int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
 
    std::vector<int>network(n+1, 0);
 
    for (int i = 0; i < n; ++i) {
 
        std::queue<int>queue;
        queue.emplace(i);
 
        while (queue.empty() == false) {
 
            auto frontNode = queue.front();
            queue.pop();
 
            for (int j = 0; j < computers[frontNode].size(); ++j) {
 
                if (computers[frontNode][j] == 1 && g_visited[j] == false) {
                    g_visited[j] = true;
                    queue.emplace(j);
                    network[i]++;
                }
            }
        }
    }
 
    answer=std::count_if(network.begin(), network.end(), [](auto& value) {
        return value > 0;
    });
 
    return answer;
}
 

 

후기

이 문제를 해결하기 위한 키워드는 BFS/DFS이다.

 

이 문제는 컴퓨터와 연결된 간선(네트워크)이 몇 개인지 알아내는 문제이다.  UNION_FIND 알고리즘으로도 풀이가 가능하다고 본다. 

 

문제의 핵심은 다음과 같다.

 

1. 먼저 컴퓨터의 개수 n개 만큼n개만큼 vector을 준비하고 n개만큼 반복문을 돌아서 서로 연결된 간선인지 확인한다.

 

2. 만약 아직 방문하지 않은 노드(false)상태이면 true 상태로 바꾸고 해당 노드와 연결된 모든 노드를 true로 바꾸면서 vector [n]의 값을 증가시킨다.

 

3. 반복문을 전부돌고 network의 개수에서 0개 이상인 원소 값을 count_if 함수를 통해 찾아낸 후 반환한다.

 

 

 

출처 및 레퍼런스

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/43162

 

관련 글

[자료구조 알고리즘/탐색 알고리즘(Search)] - [알고리즘] 너비 우선 탐색(Breadth First Search)

[온라인 코딩/탐색(Search)] - [백준] 1260번 DFS와 BFS

[온라인 코딩/탐색(Search)] - [백준] 2606번 바이러스

[온라인 코딩/탐색(Search)] - [프로그래머스] 경주로 건설