Pythonで接続して作れる最長スティックの長さを求めるプログラム

整数のリスト sticks があるとします。リストの各要素は両端を持つ1本の棒（スティック）を表しており、各端の値は 1〜6 の範囲に収まっています。2本の棒は、どちらかの端の値が一致していれば連結することができ、連結後の棒の端は「余った側の端」になり、全体の長さは伸びていきます。このとき、作れる中で最も長い棒の長さを求めるのがこの問題の目的です。

たとえば、入力が sticks = [[2, 3], [2, 4], [3, 5], [6, 6]] の場合、出力は 3 になります。[2, 3] と [2, 4] を連結して [3, 4] を作り、さらにそれと [3, 5] を連結することで [4, 5] という棒が得られるためです。

解き方のアプローチ

この問題は、棒を「頂点（端の数字）」と「辺（棒そのもの）」からなるグラフとみなし、深さ優先探索（DFS）で最長の経路（連結数）を求めることで解けます。手順は以下の通りです。

• dfs() 関数を定義します。引数は node（現在の頂点）、edge_idx（辺のインデックス）、visited（使用済みの辺を記録するセット）です。

• edge_idx が null でない場合：

  • edge_idx がすでに visited に含まれていれば 0 を返します。

  • edge_idx を visited に追加します。

  • res := 0 と初期化します。

  • g[node] に属する各 e_idx について：

    • n_node := sticks[e_idx][1] == node なら sticks[e_idx][0]、そうでなければ sticks[e_idx][1]（反対側の端）とします。

    • res := max(res, 1 + dfs(n_node, e_idx, visited)) で最大値を更新します。

  • edge_idx が非ゼロの場合、visited から edge_idx を削除して元に戻します。

  • res を返します。

• メイン処理では以下を実行します。

• sticks をタプルのリスト [(s[0], s[1]) for s in sticks] に変換します。

• 空のセット vertices と、空のマップ g（defaultdict）を用意します。

• 各インデックス i と各 edge について：

  • g[edge[0]] と g[edge[1]] に i を追加します。

  • edge[0] と edge[1] を vertices に追加します。

• res := 0 とし、vertices 内の各頂点 v に対して res := max(res, dfs(v, None, set())) を計算します。

• res - 1 を返します。連結した棒の本数（辺の数）がそのまま長さになるため、1 を引いています。

実装例

理解を深めるために、以下の実装例を見てみましょう。

from collections import defaultdict

class Solution:
    def solve(self, sticks):
        def dfs(node, edge_idx, visited):
            if edge_idx is not None:
                if edge_idx in visited:
                    return 0
                visited.add(edge_idx)
            res = 0
            for e_idx in g[node]:
                n_node = sticks[e_idx][0] if sticks[e_idx][1] == node else sticks[e_idx][1]
                res = max(res, 1 + dfs(n_node, e_idx, visited))
            if edge_idx:
                visited.remove(edge_idx)
            return res

        sticks = [(s[0], s[1]) for s in sticks]
        vertices = set()
        g = defaultdict(set)
        for i, edge in enumerate(sticks):
            g[edge[0]].add(i)
            g[edge[1]].add(i)
            vertices.add(edge[0])
            vertices.add(edge[1])
        res = 0
        for v in vertices:
            res = max(res, dfs(v, None, set()))
        return res - 1

ob = Solution()
sticks = [
    [2, 3],
    [2, 4],
    [3, 5],
    [6, 6]
]
print(ob.solve(sticks))

入力

sticks = [ [2, 3], [2, 4], [3, 5], [6, 6] ]

出力

3