以下のすべての問題はプログラマから提供されています.ありがとうございます.

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例