[bfs] 1. ネットワーク

3647 ワード
BFS テキストリンク
以下のすべての問題はプログラマから提供されています.ありがとうございます.

1.ネットワーク


問題の説明


ネットワークとは、コンピュータ間で情報を交換する接続形式を指す.例えば、コンピュータAがコンピュータBに直接接続され、コンピュータBがコンピュータCに直接接続されている場合、コンピュータAとコンピュータCは間接的に接続されて情報を交換することもできる.そのため、コンピュータA、B、Cは同じネットワーク上に存在する.
指定されたコンピュータの個数nが、接続情報を含む2次元配列コンピュータをパラメータとする場合、ネットワークの個数を返すために解関数を記述します.

せいげんじょうけん

  • コンピュータの数nは、1つまたは複数の200以下の自然数である.
  • 各コンピュータは、0からn−1までの整数として表される.
    • コンピュータ番号が
  • iの場合、コンピュータ[i][j]は1として表される.
  • コンピュータ[i][i]は常に1である.

    • I/O例



    に答える

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

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    vector<int> check(computers.size(), 0); // 배열로 써도 될듯
    queue <int> q;
    int index = 0;
    int tmp;
    for(int i = 0; i < computers.size(); i++)
    {
        // if(check[i] == 1)
        //     continue;
        if (check[i] == 0)
        {
            q.push(i);
            answer++;
            check[i] = 1;
        }
        while(!q.empty())
        {
            tmp = q.front();
            q.pop();
            for(int j = 0; j < n; j++)
            {
                if(computers[tmp][j] == 1 && check[j] == 0)
                {
                    check[j] = 1;
                    q.push(j);
                }
            }
        }
    }
    return answer;
}

    説明:

  • !(bfsコース)[https://www.youtube.com/watch?v=66ZKz-FktXo&t=336s&ab_channel=%EB%8F%99%EB%B9%88%EB%82%98]
  • この問題は最初はdfsで解くこともbfsで解くこともできますが、bfsを練習したいので解いてみました.
  • という問題では、ノードが接続されているコンピュータは、キューの深さが1つ増加するごとに、発生する可能性のあるすべての値を加算します.
  • と1つ1つが流行し,すべての状況の数を順次探索する過程である.

    • 2.ワード変換


    問題の説明


    2つの単語begin、target、単語の集合語があります.次のルールを使用して、beginからtargetに変換する最短変換プロセスを検索します.

  • 一度に1つのアルファベット
  • しか置き換えられません.
  • 個の単語にしか変換できません.
    たとえば、beginが「hit」、targetが「cog」、単語が「hot」、「dog」、「lot」、「log」、「cog」の場合、「hit」->「hot」->「dog」->「cog」の4つのステップで変換できます.
    • 2つの単語begin、target、および単語の集約語をパラメータとして指定する場合は、少なくともいくつかのステップを経てbeginをtargetに変換するには、解法関数を記述します.

    せいげんじょうけん


    各単語はアルファベット小文字のみで構成されます.
  • 各単語の長さは3または10を超えず、すべての単語の長さは同じである.
  • 個の単語は3個または50個以上の単語があり、重複する単語はありません.
  • beginとtargetは異なります.
  • が変換できない場合は0を返します.

    • I/O例


    keras中国語ドキュメントノート10——データ前処理
    2週間の最初のプロジェクトの後期...