3
0

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種類があったみたいですね。
こういう探索アルゴリズム自体、触ったことがなかったので、新鮮でした。

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


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

3
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
3
0