[C++]level 3ネットワーク43162

📌 ネットワーク

問題の説明
ネットワークとは、コンピュータ間で情報を交換する接続形式を指す.例えば、コンピュータAがコンピュータBに直接接続され、コンピュータBがコンピュータCに直接接続されている場合、コンピュータAとコンピュータCは間接的に接続されて情報を交換することもできる.そのため、コンピュータA、B、Cは同じネットワーク上に存在する.
指定されたコンピュータの個数nが、接続情報を含む2次元配列コンピュータをパラメータとする場合、ネットワークの個数を返すために解関数を記述します.
せいげんじょうけん
コンピュータの個数nは、1又は複数の200以下の自然数である.
各コンピュータは0からn−1までの整数で表される.
i番コンピュータがj番コンピュータに接続されている場合、コンピュータ[i][j]は1として表される.
コンピュータ[i][i]は常に1.
I/O例

(1) 
n = 3, computers = [[1, 1, 0], [1, 1, 0], [0, 0, 1]] 일 때
return 2
----------
(2)
n = 3, computers = [[1, 1, 0], [1, 1, 1], [0, 1, 1]] 일 때
return 1

📌に答える

注意すべき点は2つあります.
まず、最初のI/O例(2)のように接続されたネットワークであれば、数に注意してください.

   [1][2][3] //idx값을 편의상 1,2,3번으로 두겠음
[1] 1  1  0
[2] 1  1  1
[3] 0  1  1

の場合、このマトリクスから接続されたネットワークには対角線は含まれません.
(1,2)-(2,1)/(2,3)-(3,2).

そうなると、ネットの数は2ではなく1で、原因は
1.対角線(行==列)対称行列.
2.対称行列の意味は無方向図である.
3.方向がないため、この3つのノードは互いに接続することができる.
すなわち、1−>2−>3または3−>2−>1であり、ネットワーク数は1である.
最初はそれを考えずに探索したが、答えはおかしい.ああ...
第二に、二次元マトリクス、ナビゲーションに注意してください!

📌コード#コード#

深さ優先ナビゲーション(DFS)による

の実装/再バインド

#include <string>
#include <vector>
using namespace std;

bool visit[200] = {
    false,
};

void dfs(int start, vector<vector<int>> computers)
{
    visit[start] = true; //방문
    for (int i = 0; i < computers[start].size(); i++)
    {
        if (i != start && !visit[i] && computers[start][i] == 1)
        { //대각선, 방문 제외 + 이번에 방문할 친구가 1이라면
            dfs(i, computers);
        }
    }
}

int solution(int n, vector<vector<int>> computers)
{
    int answer = 0;

    for (int i = 0; i < computers.size(); i++)
    { //행별로 bfs 탐색
        if (visit[i])
            continue;
        else
        {
            dfs(i, computers);
            answer++; //깊이우선탐색이니까 여기서 호출하는 dfs의 수 == 네트워크 수
        }
    }

    ret

幅優先ナビゲーション(BFS)実装//キュー

#include <string>
#include <vector>
#include <queue>
using namespace std;

bool visit[200] = {
    false,
};

void bfs(int start, vector<vector<int>> computers)
{
    visit[start] = true;

    queue<int> q;
    q.push(start);

    while (!q.empty())
    {
        int front = q.front();
        q.pop();

        for (int i = 0; i < computers[start].size(); i++)
        {
            if (!visit[i] && computers[front][i] == 1)
            {
                visit[i] = true;
                q.push(i);
            }
        }
    }
}

int solution(int n, vector<vector<int>> computers)
{
    int answer = 0;

    for (int i = 0; i < computers.size(); i++)
    { //행별로 bfs 탐색
        if (visit[i])
            continue;
        else
        {
            bfs(i, computers);
            answer++; //너비우선탐색이니까 여기서 호출하는 bfs의 수 == 네트워크 수
        }
    }

    return answer;
}
   

参考資料