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

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

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

문제

입력&출력

문제해석

이차원배열이 주어진다. 서로 연결되어있으면 1 아니면 0으로 주어지며 자기자신과는 연결되었다라고 친다.

ex) (0,1) = 1 and (1,0)=1 이면 서로 연결 , (0,1) = 0 and (1,0)=0 이면 연결X

먼저 엑셀로 다음과 같이 구조화함 

1)DFS/BFS는 항상 visit배열, 노드는 항상 벡터로표현!!

상기 그림의 하단의 노드번호 및 연결된 노드는 Vector로 구현 

   vector<int> v[200];
   for (int i = 0; i < computers.size(); i++)
   {
      for (int j = 0; j < computers[i].size(); j++)
      {
         if (computers[i][j] == 1)
            v[i].push_back(j);
      }
   }

2) BFS 구현 

   for (int i = 0; i < n; i++)
   {
      if (v[i].size() == 0)
         continue;
      if (vi[i])
         continue;
      queue<int> q;
      q.push(i);
      vi[i] = true;
      while (!q.empty())
      {
         int x = q.front();
         q.pop();

         for (int w = 0; w < v[x].size(); w++)
         {
            if (!vi[v[x][w]])
            {
               vi[v[x][w]] = true;
               q.push(v[x][w]);
            }
         }
      }
      answer++;
   }

BFS을 이용해 한번에 모든 노드를 순회하면 네트워크는 = 1 

그 외에 여러번 순회 (= 끊겨있는 노드일때) answer++ 해주며 끊긴만큼 네트워크를 늘림.

 

난이도

★★★☆☆

실수

스스코드

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

using namespace std;

int solution(int n, vector<vector<int>> computers) {
   int answer = 0;
   vector<int> v[200];
   bool vi[200] = { false, };

   for (int i = 0; i < computers.size(); i++)
   {
      for (int j = 0; j < computers[i].size(); j++)
      {
         if (computers[i][j] == 1)
            v[i].push_back(j);
      }
   }

   for (int i = 0; i < n; i++)
   {
      if (v[i].size() == 0)
         continue;
      if (vi[i])
         continue;
      queue<int> q;
      q.push(i);
      vi[i] = true;
      while (!q.empty())
      {
         int x = q.front();
         q.pop();

         for (int w = 0; w < v[x].size(); w++)
         {
            if (!vi[v[x][w]])
            {
               vi[v[x][w]] = true;
               q.push(v[x][w]);
            }
         }
      }
      answer++;
   }
   return answer;
}