新人SEの学習記録

14年度入社SEの学習記録用に始めたブログです。気づけば社会人3年目に突入。

学習記録:プログラミングコンテスト攻略ガイド

[学習記録]プログラミングコンテスト攻略ガイド

内容

5章:全探索(続き)
  • 深さ優先探索幅優先探索
    • 深さ優先探索
      • スタックや再帰を使用して実現
      • ノードの下端まで行ってから戻ってくる
      • 全通りを列挙して結果をまとめる場合などに使用
    • 幅優先探索
      • キューを使用して実現
      • 頂点から一つずつ深く探索していく
      • 始点から最も近いもの、探索範囲が広いものなどに使用
  • 問題:迷路
    • string[]で迷路( . が通行可能、 X が通行不可)が与えられる
    • 開始位置startRow, startColが与えられる
    • 迷路挑戦者が取れる動きmoveRowとmoveColが与えられる
      • moveRow = {1, 0, 2}, moveCol = {0, 1, -1}の場合、とれる動きは(1, 0), (0, 1), (2, -1)の3つ
      • 通行不可の場所には止まれないが、その上を移動することはできる
    • 挑戦者はなるべく最短で出口に行こうとする
    • 出口を迷路上の . のどこかに置いたとき、もっとも移動する回数が多い回数を求めよ
      • ただし、どうしても移動できない出口が存在する場合は、-1を返す
  • 解き方
    • 出口を全通り試して、それぞれについて最短経路を探し、最も多い回数を…という解法は余りに計算量が多すぎる
    • とりあえず開始位置から動き回らせ、各 . についての最短移動回数を求める
    • そして . の中で最も大きな移動回数を求める
    • 自分の解法は以下
      • 被りの少ない幅優先探索の方が良さそうだが、良くわかっていないので再帰を使った
      • 各地点への移動距離を保持したmoveCount[]配列を作り、初期値として-1を入れる
      • ひたすら動き回らせてmoveCountを更新していき、既にmoveCountが自分がその地点に来た回数より少ない値で更新されていたら終了
      • 最終的に、moveCountの一番大きい値を返す
      • ただし、迷路が . でかつmoveCountが-1な地点が存在したら-1を返す
        static string[] lab;
        static int[,] moveCount;
        static int[] moveX;
        static int[] moveY;
        static int length;
        static int height;
        static int moveNum;

        static void Move(int x, int y, int curMove)
        {
            if (moveCount[y, x] != -1 && curMove >= moveCount[y, x])
            {
                return;
            }

            moveCount[y, x] = curMove;

            for (int i = 0; i < moveNum; i++)
            {
                int nextX = x + moveX[i];
                int nextY = y + moveY[i];

                if (nextX >= 0 && nextX < length && nextY >= 0 && nextY < height)
                {
                    if (lab[nextY][nextX] == '.')
                    {
                        Move(nextX, nextY, curMove + 1);
                    }
                }
            }
        }

        static int calcMaxNum(string[] labyrinth, int startRow, int startCol, int[] moveRow, int[] moveCol)
        {
            lab = labyrinth;
            moveX = moveRow;
            moveY = moveCol;
            length = lab[0].Length;
            height = lab.Length;
            moveNum = moveRow.Length;
            moveCount = new int[height, length];

            for (int i = 0; i < height; i++)
            {
                for (int j = 0; j < length; j++)
                {
                    moveCount[i, j] = -1;
                }
            }

            Move(startRow, startCol, 0);

            int maxNum = 0;

            for (int i = 0; i < height; i++)
            {
                for (int j = 0; j < length; j++)
                {
                    if (moveCount[i, j] == -1 && lab[i][j] == '.')
                    {
                        return -1;
                    }
                    maxNum = Math.Max(maxNum, moveCount[i, j]);
                }
            }
            return maxNum;
        }
  • 幅優先探索を使った解き方
    • 書籍を見るとやっぱり幅優先の方が良いようなので、参考にしつつコードを書いた
    • 書き方としては以下の通り
      • 次に移動する地点を格納するキューを用意(座標を表すためqueueXとqueueYの2つ)
      • 初期位置をキューに格納し、各座標の移動回数を入れる配列countMapに、初期位置の回数として0を入れる
      • キューに値が入っている限り、ループ
      • キューから座標を取り出す
      • 取り出した座標から、次に行ける地点を計算
      • その地点のcountMapが未更新ならば、countMapを現在地点のcountMap + 1とし、地点の座標をキューに入れる
    • 書籍を参考に書いたプログラムが以下
        static int getMaxLength(string[] maze, int startCol, int startRow, int[] cols, int[] rows)
        {
            var queueX = new Queue<int>();
            var queueY = new Queue<int>();

            int width = maze[0].Length;
            int height = maze.Length;

            int[,] countMap = new int[height, width];

            for (int i = 0; i < height; i++)
            {
                for (int j = 0; j < width; j++)
                {
                    countMap[i, j] = -1;
                }
            }

            countMap[startRow, startCol] = 0;

            queueX.Enqueue(startCol);
            queueY.Enqueue(startRow);

            while (queueX.Count > 0)
            {

                int x = queueX.Dequeue(),
                    y = queueY.Dequeue();

                int curCount = countMap[y, x];

                for (int i = 0; i < cols.Length; i++)
                {
                    int nextX = x + cols[i],
                        nextY = y + rows[i];

                    if (nextX >= 0 && nextX < width && nextY >= 0 && nextY < height && maze[nextY][nextX] == '.' && countMap[nextY, nextX] == -1)
                    {
                        queueX.Enqueue(nextX);
                        queueY.Enqueue(nextY);
                        countMap[nextY, nextX] = curCount + 1;
                    }
                }
            }

            int max = 0;

            for (int i = 0; i < height; i++)
            {
                for (int j = 0; j < width; j++)
                {
                    if (maze[i][j] == '.' && countMap[i, j] == -1)
                    {
                        return -1;
                    }

                    max = Math.Max(max, countMap[i, j]);
                }
            }

            return max;
        }
    • 全探索=再帰だと勝手に思っていたのでループだけで全探索が出来るというのが意外
    • キューによる実装も最初はコードを見てもよくわからなかった
    • 今後はなるべく再帰を使わずに、幅優先探索を使って問題を解いてみたい
  • 以下は5章で解いたその他の問題(深さ/幅優先探索とは無関係)
  • 問題:友達の数
    • 問題概要
      • SNSにおける友達の数を求める
      • お互いに友人なら、もしくは共通の友人を持っていれば「友達」となる
      • 文字列配列friends[]が与えられ、iさんとjさんが友人ならfriends[i]のj文字目はYで、そうでなければN
      • 最も人気のある人=友達の数が最も多い人の友達の数を求めよ
    • 解き方
      • 一人一人について、直接の友人と、共通の友人kがいる人物を数える
      • ある人iとj(i != j)が友人がどうか判定し、友人なら数を数える
      • また、ある人k(i != k && j != k)について、iと友人かつjと友人かどうか判定し、そうなら数を加える
      • 自分の解答は以下
        static int getMaxFriendsNum(string[] friends)
        {
            int length = friends.Length;
            int ans = 0;
            
            for (int i = 0; i < length; i++)
            {
                int friendNum = 0;

                for (int j = 0; j < length; j++)
                {
                    if (i == j)
                    {
                        continue;
                    }

                    if (friends[i][j] == 'Y')
                    {
                        friendNum++;
                    }
                    else
                    {
                        for (int k = 0; k < length; ++k)
                        {
                            if (k == i || k == j)
                            {
                                continue;
                            }

                            if (friends[i][k] == 'Y' && friends[j][k] == 'Y')
                            {
                                friendNum++;
                                break;
                            }
                        }
                    }
                }

                ans = Math.Max(ans, friendNum);
            }

            return ans;
        }