【Sランク】paiza問題集の島探しをやってみた

paiza コラボキャンペーン

こういうプログラミング系の問題を解いてみるのは、久しぶりだったので 何気に難しかったけど、結果解けてとりあえずよかった

とりあえず自分の問題を解くときに考えたこととかを書いていこーと思います！

つまずいた所

最初、こんな感じの処理で島を探していました。

1. (1, 1), (1, 2), (1, 3)というように一行づつ処理を行い、島があるかを確認
2. 島があれば、その上下左右に島があるかを確認
3. 上下左右に島があれば、リストに追加

   リストは、重複値がある場合、リスト[A]に追加
   ない場合、新規の島ということで、リスト[A']に追加する。

4. 1~3を繰り返し
5. 各リストの重複値を削除
6. リストの数をカウント

例題として出されていたものは、こんな感じの島で
処理を流してみると、ちゃんと島の数が 3 と出て、出来たと思ったのですが・・・

  1 2 3 4 
1 □ ■ ■ □ 
2 ■ □ ■ □ 
3 ■ □ □ □ 
4 □ □ ■ ■ 
5 □ ■ ■ ■ 

こういう形の場合だと、島のカウントが重複するようになってしまいました。

  1 2 3 4 
1 □ □ ■ ■ 
2 ■ ■ ■ ■ 

問題としては、左上から右下に向かって処理をしているので
(1, 3)の島と(1, 2)の島の関連性が見つけられず、この部分で重複が発生してたということみたいでした。

んで、色々ごちゃごちゃやってみた結果、うまくいったので書いていきます！

うまくいった処理

島を見つけたら、その上下左右に島が探して、また、島があれば上下左右探して・・・
という感じで、再帰的に関連する島を見つけるようにすることで、うまくいくようになりました。（ぱちぱち

今回作成した、プログラムはこんな感じです。

int row = 5;
int column = 5;
int[,] islands = {
    { 0,0,1,0,1 },
    { 1,1,1,1,0 },
    { 0,0,1,0,1 },
    { 1,1,0,1,0 },
    { 0,0,1,1,1 }
};

private int irandSearchCount()
{
    var islandList = new List<List<Tuple<int, int>>>();
    // 処理済 履歴用リスト
    var historyList = new List<Tuple<int, int>>();

    for (int i = 0; i < row; i++)
    {
        for (int j = 0; j < column; j++)
        {
            // 既に処理が行われていないものを実施
            var current = Tuple.Create(i, j);
            if (!historyList.Contains(current) && islands[i, j] == 1)
            {
                // 発見した島のリスト
                var foundList = new List<Tuple<int, int>>();

                // taskListの処理を実施
                IlandSearch(ref foundList, new List<Tuple<int, int>>() { current });

                if (foundList.Count() > 0)
                {
                    historyList.AddRange(foundList);
                    islandList.Add(foundList);
                }
            }
        }
    }
    return islandList.Count;
}

private void IlandSearch(ref List<Tuple<int, int>> foundList, List<Tuple<int, int>> taskList)
{
    // 処理を行うものがなくなったら終了
    if (taskList.Count() <= 0) return;

    var newTaskList = new List<Tuple<int, int>>();

    for (int i = taskList.Count() - 1; i >= 0; i--)
    {
        int x = taskList[i].Item1;
        int y = taskList[i].Item2;

        // 上
        if (x - 1 >= 0 && islands[x - 1, y] == 1)
            newTaskList.Add(Tuple.Create(x - 1, y)); 
        // 下
        if (x + 1 < row && islands[x + 1, y] == 1) 
            newTaskList.Add(Tuple.Create(x + 1, y));
        // 左
        if ((y - 1) >= 0 && islands[x, y - 1] == 1) 
            newTaskList.Add(Tuple.Create(x, y - 1));
        // 右
        if (y + 1 < column && islands[x, y + 1] == 1) 
            newTaskList.Add(Tuple.Create(x, y + 1));

        // 発見した島リストに追加
        foundList.Add(Tuple.Create(x, y));
        // 処理リストから削除
        taskList.RemoveAt(i);

        // 重複する値を見つける
        var duplicates = foundList.Intersect(newTaskList).ToList();
        // list1から重複する値を削除
        newTaskList = newTaskList.Except(duplicates).ToList();
    }
    IlandSearch(ref foundList, newTaskList);
}

終わりに

一応問題も解けたし、色々と調べてみたら解き方としては、
[ 深さ優先探索 ]と[ 幅優先探索 ]の2種類があったみたいですね。
こういう探索アルゴリズム自体、触ったことがなかったので、新鮮でした。

今回、自分が解いたやり方的には、幅優先探索ぽい感じかなー。

---

読んで分かりやすかった記事