【連結の判定】STEP: 5 一方通行（グラフ上の移動） (paizaランク B 相当) 解答例 – PHP編【Aランクレベルアップメニュー】
【Aランクレベルアップメニュー】 > 【連結の判定】STEP: 5 一方通行（グラフ上の移動） (paizaランク B 相当)
※リンク先へ移動する為には「paiza」へのログインが必要です。
各頂点の移動順を探し出し、解答を出力する問題です。この問題で厄介なところは、繋がっている「a」と「b」があるとすると、「aからb」に移動するのか「bからa」に移動するのかが分からない点です。
この点はまず全ての情報を「配列[a][b]と配列[b][a]」と二つのパターンを多次元配列に格納します。始点が必ず「1」からスタートすることから、「foreach」で全ての情報から「1」を探し、結合している頂点を次の移動地点として、答えとする配列に保存していきます。次はその頂点から同じように結合している頂点を探すという作業をゴールまで繰り返します。
かなりごり押し気味ですが、自力で解いたらこんな感じになりました(;’∀’)
解答例
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
<?php $n = trim(fgets(STDIN)); //頂点の数を取得する for($i = 0;$i < $n - 1;$i++){ $test = explode(" ",trim(fgets(STDIN))); $a = $test[0]; $b = $test[1]; $array[$b][$a] = 1; //隣接している頂点の表記移動順ではない為、$aと$bを逆にしたものをキーとして保存する $array[$a][$b] = 1; //隣接している頂点の表記移動順ではない為、$aと$bを逆にしたものをキーとして保存する } $num= 1; // 検査対象の配列。始点は常に1なので始めは1をいれる $ans = array($num); //この配列に移動順を記録する for($i = 0;$i < $n - 1;$i++){ //始点1を除いた回数分以下の処理を行う foreach($array as $key1 => $value1){ foreach($value1 as $key2 => $value2){ if($key1 == $num){ //もし「$key1」が「$num」であり… if(in_array($key2 , $ans ,true) == false){ //もし「$key2」が「$ans」の中にないのならば… array_push($ans,$key2); //「$ans」に「$key2」を記録する $num = $key2; //検査対象に$key2を入れる break; } } elseif($key2 == $num){ //もし「$key2」が「$num」であり… if(in_array($key1 , $ans ,true) == false){ //もし「$key1」が「$ans」の中にないのならば… array_push($ans,$key1); //「$ans」に「$key1」を記録する $num = $key1; //検査対象に$key1を入れる break; } } } } } foreach($ans as $value){ echo $value."\n"; } ?> |
