そまちょブログのそまちょ（@somachob）です。
この記事は、AtCoder Beginner Contest 317 の C問題についての解説です。
C – Remembering the Days
好きな街からスタートして同じ街を二度以上通らずに別の街へ移動するときの、通る道路の長さの最大値を求めます。
順列全探索
制約から N が最大で10なので、移動する街の順番を全列挙して答えを求めてみます。
順列全探索を使って、移動する街の順番を出力します。
順列は、与えられた要素を並べ替えることで得られる組み合わせです。
順列全探索については、次の記事で解説しています。
Python では、itertools モジュールを使うことで、簡単に順列を生成できます。
import itertools
A = list(range(3))
print(A) # => [0, 1, 2]
# 順列の生成
for permutation in itertools.permutations(A):
print(permutation)
"""permutations で出力した順列
(0, 1, 2)
(0, 2, 1)
(1, 0, 2)
(1, 2, 0)
(2, 0, 1)
(2, 1, 0)
"""これで移動する街の順番を全探索します。
import itertools
# 入力
N, M = map(int, input().split())
# 順列全探索
for route in itertools.permutations(range(N)):
# 訪れる街の順番について処理街と街の長さは、2次元配列で管理します。
次のような感じです。
| 街A＼街B | 1 | 2 | 3 | 4 |
| 1 | 1 | 100 | 1000 | |
| 2 | 1 | 10 | ||
| 3 | 100 | 10 | ||
| 4 | 1000 |
２次元配列はすべてを０で初期化して、街の番号 ‐１ で管理します。
たとえば、街１から街３への距離は２次元配列distance だと distance[0][2] に格納されています。
# 距離を管理する２次元配列
distance = [[0] * N for _ in range(N)]
for _ in range(M):
A, B, C = map(int, input().split())
A -= 1
B -= 1
distance[A][B] = C
distance[B][A] = C
print(distance)
"""入力例１の出力結果(見やすく加工しています)
[
[ 0, 1, 100, 1000],
[ 1, 0, 10, 0],
[100, 10, 0, 0],
[1000, 0, 0, 0]
]
"""ここで大事なのが、２次元配列の初期値のままのところは、街から街への道路がないことを意味します。
移動する街の距離を求める
街から街の距離を合計していきます。
順列全探索で移動する街の順番が生成されます。
その順列に従って、順番に街を移動します。
# 順列全探索
for route in itertools.permutations(range(N)):
# 生成した順番で街を移動するときの距離の合計
total_distance = 0
# 街を順番に移動する
for i in range(N - 1):
city_A = route[i]
city_B = route[i + 1]
# 街 A と 街 B がつながっていないとき
if distance[city_A][city_B] == 0:
break
total_distance += distance[city_A][city_B]あとは、距離の最大値を求めます。最終的なコードは次のようになります。
import itertools
# 入力
N, M = map(int, input().split())
# 距離を管理する２次元配列
distance = [[0] * N for _ in range(N)]
for _ in range(M):
A, B, C = map(int, input().split())
A -= 1
B -= 1
distance[A][B] = C
distance[B][A] = C
# 答えを格納する変数
answer = 0
# 順列全探索
for route in itertools.permutations(range(N)):
# 生成した順番で街を移動するときの距離の合計
total_distance = 0
# 街を順番に移動する
for i in range(N - 1):
city_A = route[i]
city_B = route[i + 1]
# 街 A と 街 B がつながっていないとき
if distance[city_A][city_B] == 0:
break
total_distance += distance[city_A][city_B]
# 距離が大きい方を格納
answer = max(answer, total_distance)
print(answer)深さ優先探索
街から街への連結をグラフとして受け取り、深さ優先探索をすることでも解くことができます。
# スタックサイズの変更
import sys
sys.setrecursionlimit(10**6)
# 入力
N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
A, B, C = map(int, input().split())
A -= 1
B -= 1
graph[A].append((B, C))
graph[B].append((A, C))
# 深さ優先探索
def dfs(city):
# v 地点を探索済みに
visited[city] = True
total_distance = 0
# 取り出した地点から行ける地点について繰り返す
for next_city, distance in graph[city]:
# 行ける地点が探索済みならスキップ
if visited[next_city]:
continue
# 行ける地点について再帰的に探索
total_distance = max(total_distance, distance + dfs(next_city))
visited[city] = False
return total_distance
answer = 0
visited = [False] * N
# 各街から深さ優先探索
for start_city in range(N):
answer = max(answer, dfs(start_city))
print(answer)
