Programmers_네트워크

3레벨이여서 풀었는데 문자열구현하는 2레벨 문제보다 훨씬 쉬웠다. 구현문제 열심히좀 풀자...😭

• 필자는 BFS로 문제를 풀어냈다.

• A B C가 있을때, A와B가 연결되어있고 B와C가 연결되어있으면 A와 C가 연결되어있다는 원리.

• 그래서 필자는 BFS 에서 check를 활용해서 문제를 풀어냈다.

• BFS를 돌면서 queue에 들어간(네트워크에 연결된) 값을 check[i]=1을 해준다.

• main문에서 컴퓨터의 수만큼 for문을 돌면서 check값이 1이면 continue 시켜주는 방식이다.

• 예를들어, 1번 컴퓨터를 bfs에 넣어주고 돌리면 1번 컴퓨터와 연결되어있는 컴퓨터는들은 check값이 1이 된다.

  • check가 1이된 컴퓨터들은 bfs에 넣어주지 않는다.
  • 이러면 네트워크가 몇개인지 알아낼 수 있다.
  • 설명하면서 무슨말인가 싶다. 코드로 보자...

💻전체코드

#include <string>
#include <vector>
#include <queue>

using namespace std;

vector<int>v[201];
bool check[201];
int answer = 0;

void bfs(int num)
{
    queue<int>q;
    q.push(num);
    check[num]=1;
    answer++;
    while(!q.empty())
    {
        int cur = q.front();
        q.pop();
        for(int i=0;i<v[cur].size();i++)
        {
            if(check[v[cur][i]]) continue;
            check[v[cur][i]]=1;
            q.push(v[cur][i]);
        }
    }
}

int solution(int n, vector<vector<int>> computers) {
    
    //computers 배열을 통해 연결되어있는 모든 값을 vector로 구현.
    for(int i=0;i<computers.size();i++)
    {
        for(int j=0;j<computers[i].size();j++)
        {
            if(computers[i][j])
                v[i].push_back(j);
        }
    }
    
    // 0번부터 n-1번 컴퓨터까지 돌리며, check값에 따라 bfs를 돌려준다.
    // check값이 1인 경우는 이미 전에 돌렸던 컴퓨터과 같은 네트워크이기에 또 세줄 필요가 없다. 
    for(int i=0;i<computers.size();i++)
    {
        if(check[i]) continue;
        bfs(i);
    }
    
    return answer;
}

bfs는 쉽다. 구현좀 더 풀자.