✏️

幅優先探索を用いて木構造の頂点間の最短経路を求める

2022/10/01に公開約2,500字

こんにちは。つくねです。

今回は「トヨタ自動車プログラミングコンテスト2022(AtCoder Beginner Contest 270) C - Simple path」について、幅優先探索を用いて木構造の頂点間の最短経路を求めてみたいと思います。使用する言語はJavaです。

  • 隣接リストの作成
  • 幅優先探索の準備
  • 幅優先探索の実施
  • 経路復元

上記のリストの順番で答えを導出する方針で解答します。

サンプル 入力例

5 2 5
1 2
1 3
3 4
3 5

入力から作成できる木は下記のようなイメージです。2から5までの最短経路を求めたいです。

隣接リストの作成

Scanner sc = new Scanner(System.in);

int N = sc.nextInt();
int X = sc.nextInt();
int Y = sc.nextInt();

int[] U = new int[N + 1];
int[] V = new int[N + 1];

for(int i = 1; i <= N - 1; i++) {
	U[i] = sc.nextInt();
	V[i] = sc.nextInt();
}

// 隣接リストの作成
ArrayList<Integer>[] adjacent = new ArrayList[N + 1];
for(int i = 1; i <= N; i++) {
	adjacent[i] = new ArrayList<Integer>();
}
for(int i = 1; i <= N - 1; i++) {
	adjacent[U[i]].add(V[i]);
	adjacent[V[i]].add(U[i]);
}

幅優先探索の準備

今回でいうと、入力Xがスタート地点になるので、

それに合わせて1番最初にキューに挿入するのを「X」とします。

// 幅優先探索の初期化
int[] dist = new int[N + 1];
for(int i = 1; i <= N; i++) {
	dist[i] = -1;
}

// スタートの決定
Deque<Integer> que = new ArrayDeque<>();
dist[X] = 0;
que.add(X);

幅優先探索の実施

キューを用いて幅優先探索を行っていきます。ここは1度、図にして頭の中で整理しました。慣れている人は「はいはいアレね」といった感じで解いていくんでしょうね…恐れ入ります。

// 幅優先探索で最短距離を求める
while(que.size() >= 1) {
	int pos = que.remove();
	for(int i = 0; i < adjacent[pos].size(); i++) {
		int nex = adjacent[pos].get(i);
		if(dist[nex] == -1) {
			dist[nex] = dist[pos] + 1;
			que.add(nex);
		}
	}
}

経路復元

先ほどまでのプログラムで、頂点Xから各頂点までの最短距離を求めることはできましたが、求められている答えとしては、「経路」になるので、最短距離から経路を復元していきます。問題の前提で、「木上の任意の相異なる 2頂点 a,bについて、a から bへの単純パスがただ一つ存在することが証明できます」とあるので、ゴール(頂点Y)から逆にたどっていって、頂点Xまで戻るまで各頂点をたどっていきます。

// 経路がただ1つ決定することに基づく
while(nowPos != X) {
	for(int i = 0; i < adjacent[nowPos].size(); i++) {
		if(dist[adjacent[nowPos].get(i)] == nowDist - 1) {
			nowDist--;
			nowPos = adjacent[nowPos].get(i);
			anser.add(nowPos);
		}
	}
}

// 結果出力
for(int i = anser.size() - 1; i >= 0; i--) {
	System.out.print(anser.get(i));
	System.out.print(" ");
}

ひとまず、これで求められている答えを出力することができました。

編集後記

今回はAtcoderで出題された問題を題材に、人生ではじめて記事を書いてみましたが、無茶苦茶時間かかりますね。コレ。自己紹介もなしに記事を書き始めましたが、タイトルと違うことを最初に書くのもヘンだなと思い、ここでちょこっとだけさせてください。私の技術背景ですが、2022年の7月ごろからAtcoderを初めて、やっと灰色の真ん中ぐらいに到達した、プログラミングド素人です。新卒から入社して2年半たちましたが、調整業務や委託管理ばかりで、全くプログラミングをしていません。「アウトプットすることが大事!」という記事をどこかで見て、「確かに」と思い、執筆に至りました。先人たちが書いている記事に比べたらちっぽけなものかもしれないですが、”塵積”ということで、自分の辿ってきた轍となればなと思っております。少しでも興味を持っていただいたら幸いです。

おわり

Discussion

ログインするとコメントできます