思考力を試す「ナゾ解き」連載がスタート！出題者は、アルゴリズムの書籍や競技プログラミングの解説記事を多数執筆する大槻兼資さんです。テーマは、実社会で数学がどう使われているか。楽しみながら学べる問題をお届けします。今回は読者プレゼントもご用意しました。詳細は記事のさいごに。
読者の中には、中学校や高校で数学の学習に苦しんだ方もいるかもしれません。「こんなことを学んで何の役に立つのだろうか？」と感じた方も多いかもしれません。しかしながら、数学は私たちの暮らす社会の中で、さまざまに使われています。本連載では、実際に社会の中で役に立っている数学を題材として、簡単なクイズを出題していきます。学生時代に数学が苦手だった方も、ぜひ肩の力を抜いて、挑戦してみてください！ 大槻兼資
問題
下の図のような迷路を考えます。
スタート（S）からゴール（G）まで行きたいとします。1回の移動では、現在いるマスから、隣接する上下左右のマスに移動することができます（これを1手とします）。ただし茶色のマスは壁を表しており、入ることができません。
SのマスからGのマスまで最短で何手で到達できるでしょうか。
例題
たとえば、下の図の小さな迷路では、赤丸で示したマスを辿っていくのが最短です。Sのマスから9手でGのマスまで到達できます。
アドバンスト
この問題が難なく解けたという方は、迷路の大きさが1000×1000になっても、コンピュータを活用して解くことのできる方法を考えてみてください。
クイズの応用例
このクイズの解法はこれから示しますが、その解法は、現実世界のさまざまなサービスにも応用されています。
- カーナビ（現在地から目的地への最短経路を示します）
- 電車の乗り換え案内サービス（現在駅から目的駅への最短経路を示します）
- 宇宙の地球外惑星を探索するローバー（ローバーの探索アルゴリズムに使われています）
などは、代表的な応用例だと言えるでしょう。
解答
それでは、正解を発表します。
・
・
・
正解は27です。下の図の経路が最適解です。
みなさんは正答できたでしょうか。できた方は、なぜこの経路が最適なのか、その理由まで考えてみましょう。
解説
それでは、解説を始めます。 まず、下の図のように、Sのマスから1手で行けるマスに「1」と数値を書き込みます。
次に、下の図のように、「1」と書かれたマスから1手で行けるマスに「2」と数値を書き込みます。ただし、すでに数値の書かれているマスには書き込みません。これらのマスはスタートから2手で行けるマスでもあります。
さらに、下の図のように、「2」と書かれたマスから1手で行けるマスに「3」と数値を書き込みます。これらのマスはスタートから3手で行けるマスでもあります。
これ以降も同様に、4、5、6、......と数値を書き込んでいくと、最終的には下の図のように、Gのマスに27と書き込まれます。
以上より、SのマスからGのマスへ至るまでの最短経路の長さが27であることがわかりました。
なお、具体的な最短経路は下の図のようになります。今度はGのマスから出発して、書かれた数が1ずつ下がっていくようなマスを選んでいくことで、具体的な最短経路を求めることができます。
おわりに
最後に、このクイズの解法と数学との関連を紹介します。
私たちは「すでに数が書き込まれたマスの数を用いて、新しいマスに書き込む数を求める」という方法で最短経路を求めました。このような、すでにわかっている値を用いて、わかっていない値を求めていくという考え方は、数学Bの単元「数列」に登場する漸化式でもお馴染みです。
次回も、漸化式の考え方を用いて解くことのできるパズルを出題します。ぜひ、楽しみにしてください！
アドバンス問題の解答
以下は、迷路の大きさが1000×1000になっても、コンピュータを活用して解くことのできる方法についてです。C++で記述しています。
# include <iostream>
# include <queue>
# include <vector>
# include <string>
# include <iomanip>
using namespace std;
/* 4 方向への隣接頂点への移動を表すベクトル */
const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };
int main() {
////////////////////////////////////////
/* 入力受け取り */
////////////////////////////////////////
/* 縦と横の長さ */
int height, width;
cin >> height >> width;
/* 盤面 */
vector<string> field(height);
for (int h = 0; h < height; ++h) cin >> field[h];
/* スタート地点とゴール地点 */
int sx, sy, gx, gy;
for (int h = 0; h < height; ++h) {
for (int w = 0; w < width; ++w) {
if (field[h][w] == 'S') {
sx = h;
sy = w;
}
if (field[h][w] == 'G') {
gx = h;
gy = w;
}
}
}
////////////////////////////////////////
/* 幅優先探索の初期設定 */
////////////////////////////////////////
// 各セルの最短距離 (訪れていないところは -1 としておく)
vector<vector<int> > dist(height, vector<int>(width, -1));
dist[sx][sy] = 0; // スタートを 0 に
// 探索中に各マスはどのマスから来たのかを表す配列 (最短経路長を知るだけなら、これは不要)
vector<vector<int> > prev_x(height, vector<int>(width, -1));
vector<vector<int> > prev_y(height, vector<int>(width, -1));
// 「一度見た頂点」のうち「まだ訪れていない頂点」を表すキュー
queue<pair<int, int> > que;
que.push(make_pair(sx, sy)); // スタートを push
////////////////////////////////////////
/* 幅優先探索を実施 */
////////////////////////////////////////
/* キューが空になるまで */
while (!que.empty()) {
pair<int, int> current_pos = que.front(); // キューの先頭を見る (C++ ではこれをしても pop しない)
int x = current_pos.first;
int y = current_pos.second;
que.pop(); // キューから pop を忘れずに
// 隣接頂点を探索
for (int direction = 0; direction < 4; ++direction) {
int next_x = x + dx[direction];
int next_y = y + dy[direction];
if (next_x < 0 || next_x >= height || next_y < 0 || next_y >= width) continue; // 場外アウトならダメ
if (field[next_x][next_y] == '#') continue; // 壁はダメ
// まだ見ていない頂点なら push
if (dist[next_x][next_y] == -1) {
que.push(make_pair(next_x, next_y));
dist[next_x][next_y] = dist[x][y] + 1; // (next_x, next_y) の距離も更新
prev_x[next_x][next_y] = x; // どの頂点から情報が伝播して来たか、縦方向の座標をメモ
prev_y[next_x][next_y] = y; // どの頂点から情報が伝播して来たか、横方向の座標をメモ
}
}
}
////////////////////////////////////////
/* 結果出力 */
////////////////////////////////////////
int x = gx, y = gy;
while (x != -1 && y != -1) {
field[x][y] = 'o'; // 通過したことを示す
// 前の頂点へ行く
int px = prev_x[x][y];
int py = prev_y[x][y];
x = px, y = py;
}
for (int h = 0; h < height; ++h) {
for (int w = 0; w < width; ++w) {
cout << std::setw(3) << field[h][w];
}
cout << endl;
}
cout << dist[gx][gy] << endl;
}
このプログラムに対して、次の値（例題）を入力してみましょう。
4 5
…#G
…#.
.#...
S.#..
すると、次のように、例題の答えである経路が出力されます。
. . . # o
o o o # o
o # o o o
o . # . .
9
読者プレゼント！
このクイズの感想をお送りいただいた方の中から、抽選で書籍『パズルで鍛えるアルゴリズム力（技術評論社）』をプレゼント！
『もっと難しい問題がいい』『今回がちょうど良かった』など、問題の難易度についてのご意見もぜひお聞かせください。ご応募お待ちしています！
プレゼントの応募は締め切りました。たくさんのご応募ありがとうございました。
筆者・出題者：大槻 兼資さん
株式会社 NTT データ数理システム顧問、モノグサ株式会社コンテンツアーキテクト。数学や情報科学の諸分野の教材開発や啓蒙活動に従事。「けんちょん」の愛称で親しまれている。著書に『問題解決力を鍛える！アルゴリズムとデータ構造』（講談社）がある。数理最適化や機械学習を活用した数理コンサルティング業務の経験も多数。趣味は競技プログラミング、虫食算作り、国内旅行など。
ファクトチェック：増井 敏克さん
増井技術士事務所代表。技術士（情報工学部門）。情報処理技術者試験にも多数合格。ビジネス数学検定1級。「ビジネス」×「数学」×「IT」を組み合わせ、コンピュータを「正しく」「効率よく」使うためのスキルアップ支援や、各種ソフトウェアの開発、データ分析などを行う。著書は『プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問』『プログラマを育てる脳トレパズル 遊んでおぼえるPythonプログラミング＆アルゴリズム』（翔泳社）など多数。
