XML解析からアルゴリズム面接へ：ある初心者の深さ優先探索 (DFS) 上達の旅

algorithm

はじめに：なぜファイル処理をするだけなのにアルゴリズムが必要なのか？

コンピュータアルゴリズムの初心者として、初めて複雑にネストされたXMLファイルに直面し、それをCSV形式に変換しようとしたとき、私の心は折れそうでした。最初は単なる「ファイルを読んで、ファイルに書き込む」だけのプロセスだと思っていたのに、「ねえ、これ実は深さ優先探索（DFS）の問題だよ」と言われたからです。

深さ優先探索？それって迷路を解くときに使うやつじゃないの？私のXMLファイルと何の関係があるの？

この記事は、私がゼロからDFSを理解し、スタック（Stack） データ構造を使ってXMLを解析し、最終的には意図せずしてアルゴリズム面接の高難易度テーマである「非再帰的な後行順回（汎用マーキング法）」に触れるまでの全過程を記録したものです。もしあなたもこれらの概念に戸惑っていたり、「再帰」と「ループ」の変換でつまづいているなら、この旅が何かのヒントになることを願っています。

第1章：直感を打ち破る——深さ優先探索とは何か？

まず、最も基本的な疑問を解決しましょう。DFSとは何でしょうか？

迷路ゲームをしている自分、あるいは多くの分かれ道がある交差点に立っている自分を想像してください。あなたの戦略はこうです。「行き止まりにぶつかるまで、ひたすら一本道を進む」。

  1. 道を選ぶ： 分かれ道に来たら、適当に一つの道を選んで入る。
  2. 突き進む： その道をひたすら進む。これ以上進めなくなるまで（袋小路、あるいはゴールに着くまで）。
  3. 戻る（バックトラック）： もし袋小路なら、来た道を戻り、一つ前の分かれ道まで下がる。
  4. 道を変える： その分かれ道で、まだ通っていない別の道を選び、再び「突き進む」。
  5. 繰り返す： すべての道を歩き終わるまで繰り返す。

なぜXMLからCSVへの変換にDFSが必須なのか？

このXML構造を見てください：

<Root>
    <ProjectInfo>
        <Name>Test Project</Name>
        <ID>12345</ID>
    </ProjectInfo>
    <Modules>
        <Module>
            <Name>Module A</Name>
            <Config><Param>Value 1</Param></Config>
        </Module>
    </Modules>
</Root>

XMLは木構造（層状のネスト）であり、CSVはフラットな構造（Excelの表のようなもの）です。 これを木として描くとこうなります：

Root (根)
├── ProjectInfo (枝)
│   ├── Name: "Test Project" (葉/データ)
│   └── ID: "12345" (葉/データ)
└── Modules (枝)
    └── Module ...

プログラムを書いてこのXMLを読み込み、CSVに変換しようとするとき、プログラムの読み取りカーソルは、あの「迷路を歩く人」と同じです。 単に <Root> の入り口をうろつくだけではだめで、中に入り（より深くへ）、<ProjectInfo> へ入り、さらに <Name> へ入って初めて、"Test Project" という具体的なデータを手に入れることができます。

重要なのは「深さ」です。中に入り込める限り、決して横へは移動しません。この「層を一枚ずつ剥がしていく」プロセスこそが、アルゴリズムでいう深さ優先探索なのです。

第2章：ツールの選択——スタック (Stack)

「何をすべきか」が分かったら、次は「どうやるか」です。もし再帰（関数が自分自身を呼び出すこと）を使わずに、どうやってループでこのプロセスを実現するのでしょうか？

私たちには核心となるデータ構造が必要です。それがスタック（Stack）です。

スタックのルール：後入れ先出し (LIFO - Last In First Out) 「スタック」は積み重ねた皿、あるいは銃の弾倉のようなものだと想像してください。

  • プッシュ (Push)： 新しい皿を一番上に置く。
  • ポップ (Pop)： 一番上の皿を取り除く。

なぜDFSにスタックが必要なのか？ DFSの戦略を覚えていますか？「行き止まりまで突き進む」です。

あるノード（例：<Root>）を処理しているとき、それに子ノード（<ProjectInfo> と <Modules>）があることに気づいたとします。「深さ優先」を実現するためには、手元にある <Root> に関する他の作業を直ちに中断し、たった今見つけた <ProjectInfo> の処理を優先しなければなりません。

これは、<ProjectInfo> というタスクをスタックの一番上（トップ）に放り込むようなものです。スタックは「後入れ先出し」なので、次のループが始まったときに手に取るタスクは、今放り込んだばかりの新しいタスクになります。箱の底にある古いタスクではありません。これによって「深層へ潜る」動きが実現されるのです。

第3章：思考の壁その1——「Pop」は「廃棄」ではない

スタックを理解する過程で、私は最初の巨大な思考の誤解にぶつかりました。

「<Root> をポップ（Pop）して取り出したら、その閉じタグはどうやってCSVに書き込むの？ 取り出しちゃったら、もう無くなっちゃうじゃないか？」

これはプログラミング的思考における非常に深い転換点です。非再帰的なスタックモードにおいて：

「スタックから出す（Pop）」は「処理終了」ではなく、「処理開始」を意味します！

例えを変えてみましょう。スタック（Stack）を「ToDoリスト」だと想像してください。

  1. 初期状態： リストには一行だけ【<Root> を処理する】と書いてあります。
  2. 第一歩（Pop）： あなたは【<Root> を処理する】という行を横線で消しました（Pop）。
  3. あなたのアクション： <Root> を捨てたのではなく、<Root> というフォルダを開いたのです。
  4. 発見： 中に2つのサブフォルダ、ProjectInfo と Modules があるのを見つけました。

  5. 反応： まだ仕事は終わっていないので、リストに新しい2行を追加しました：【ProjectInfo を処理する】と【Modules を処理する】。

  6. 結果： 【<Root> を処理する】というタスクはリスト（スタック）から消えましたが、そのタスクの実質は具体的なサブタスク（子ノード）へと変換され、リストに残り続けています。

つまり、スタックが完全に空になった瞬間こそが、すべての子孫の処理が完了したことを意味し、それはすなわち <Root> の終了と等しいのです。

第4章：思考の壁その2——前行順回と「逆順プッシュ」

実装プロセスにおいて、いくつかの二分木トラバーサル（走査）の動画を参考にしていた際、奇妙な現象に気づきました。なぜコードの中では、先に右部分木をプッシュし、その後に左部分木をプッシュしているのでしょうか？

# 動画で見た二分木DFSコード
if node.right:
    stack.append(node.right)  # 1. 先に右側を箱の底に押し込む
if node.left:
    stack.append(node.left)   # 2. 次に左側をその上に乗せる

なぜ逆にするのか？ これは完全にスタックの後入れ先出し (LIFO) 特性に合わせるためです。

  • 私たちが先に取り出して処理したいのは左側（Left / 1番目）です。
  • だからこそ、それを後で入れる必要があります。
  • 皿洗いと同じです。一番上の皿を最初に洗いたいなら、最後にそれを置かなければなりません。

XMLにおける「左右」と安定性 XMLは多分木ですが、ロジックは同じです。リスト内の最初のタグが「一番左」、最後のタグが「一番右」です。 プログラムがXMLファイルを上から下へ（左から右へ）の順序でデータを読むことを保証するために、子ノードのリストを逆順 (Reverse) にしてスタックにプッシュする必要があります。

ここで私はある懸念を抱きました。「node.get_children() で取得したリストの順序は安定しているのか？」 答えはイエスです。XMLパーサ（PythonのElementTreeなど）は、下層でツリーを構築する際、テキストファイルに出現する行番号の順序に厳密に従って子ノードをリストに格納します。<Name> が <ID> の前に書いてあれば、リスト内でも前に来ます。

したがって、安心して reversed() を使用できます：

# children = [ProjectInfo, Modules] だと仮定

# 動画でRightを先にプッシュしたように、リストを「逆順」でプッシュします
# つまり Modules を先にプッシュし（底に沈む）、最後に ProjectInfo をプッシュします（頂上に来る）
for child in reversed(children): 
    stack.append(child)

こうすることで、取り出す（出庫する）際に ProjectInfo を先に入手でき、XMLの閲覧順序を完全に再現できます。

第5章：究極の挑戦——閉じタグ（インデント問題）をどう処理するか？

読み取り順序を解決した後、最大の問題に直面しました： 「CSVには閉じタグは不要だけど、もしインデントを保持したい場合や、最後に </Root> を出力したい場合はどうすればいい？」

再帰であればこれは非常に簡単です（関数の実行が終われば自動的に戻るため）。しかしスタックのループ内では、親ノードが一度ポップされると、コンテキスト（文脈）が失われます。子供たちの処理が終わった頃には、手元にあの親ノードはもうありません。

解決策：状態マーキング法 (The Color Marking Method) スタックに入れるものを変える必要があります。以前はスタックに Node だけを入れていましたが、これからは タプル (Node, 状態) を入れます。 2つの状態を定義します：

  • ENTER (入場/開始)： 初めてこのノードに出会った状態。開始タグ <Tag> を出力し、その後、自分自身を再びスタックの底に押し戻し（後で回収するため）、子供たちの処理に向かいます。
  • EXIT (退場/閉じる)： 子供たちの処理がすべて終わり、戻ってきて後始末をする状態。</Tag> を出力します。

これこそが古典的な「二次プッシュ法（二回入栈法）」です。

Pythonコード完全実装 このロジックはXMLのインデントや閉じタグ問題を解決するだけでなく、汎用的な木構造トラバーサルのアルゴリズムテンプレートでもあります。

import xml.etree.ElementTree as ET

# 模擬データ
xml_data = """<Root>
    <ProjectInfo><Name>Test</Name></ProjectInfo>
    <Modules><Module>A</Module></Modules>
</Root>"""
root = ET.fromstring(xml_data)

# 状態定数の定義
ACTION_ENTER = "ENTER" # 入ったばかり。 <Tag> を出力する準備
ACTION_EXIT = "EXIT"   # 子供の処理完了。 </Tag> を出力する準備

# スタック構造： [ (ノードオブジェクト, アクション状態, インデントレベル) ]
stack = [(root, ACTION_ENTER, 0)]

print("--- 構造生成開始 ---")

while stack:
    node, action, level = stack.pop()
    indent = "    " * level  # インデントスペースの生成
    
    if action == ACTION_ENTER:
        # 1. 【入場アクション】開始タグの処理
        print(f"{indent}<{node.tag}>")
        
        # 2. 【魔法の鍵】二次プッシュ！
        # 自分自身を変身させて（EXIT状態）、再びスタックの底に放り込む
        # これは子供たちの処理が終わった後に浮き上がってくる「時限爆弾」を仕掛けるようなもの
        stack.append((node, ACTION_EXIT, level))
        
        # 3. そして子供たちを逆順でプッシュ（ENTER状態）
        # こうすることで、次のループでは先に子供を処理することになる（深さ優先）
        if len(list(node)) > 0:
            for child in reversed(list(node)):
                stack.append((child, ACTION_ENTER, level + 1))
                
    elif action == ACTION_EXIT:
        # 4. 【退場アクション】閉じタグの処理
        # ここに来て初めて、このノードの処理が真に終了したことを示す
        print(f"{indent}</{node.tag}>")

第6章：XMLからアルゴリズム面接への昇華

「二次プッシュ」法を理解したとき、私は驚きました。自分が無意識のうちに、アルゴリズム面接の高頻度かつ難関ポイントである「二分木の非再帰的後行順回（Post-order Traversal）」を習得していたことに気づいたのです。

LeetCode（第145問など）や面接では、面接官によくこう聞かれます。「再帰を使わずに、後行順回（左->右->根）を実装してください」。

多くの丸暗記型の人はここでつまづきます。なぜなら、非再帰の後行順回ロジックは非常に複雑だからです。しかし、私たちが先ほど使った「汎用マーキング法」（別名：カラーマーキング法）を使えば、この問題はボーナス問題に変わります。

  • 白いノード (White/Enter)： 初見。ノードを灰色にして戻し（プッシュ）、さらに右の子、左の子をプッシュする。
  • 灰色のノード (Gray/Exit)： 2回目。直接数値をプリントする。

この方法が強力なのは、統一されたテンプレートを提供してくれるからです。

  • 前行順回（Pre-order）がしたい？ プッシュの順序を変えるだけです。
  • 中行順回（In-order）がしたい？ 灰色のノード（自分）を左右の子の間に挟んでプッシュすればいいのです。
  • 後行順回（Post-order）がしたい？ 自分を最初にプッシュし（底に沈める）、その後に子供をプッシュします。

結び

今回のXMLファイル解析からCSV変換への議論を通じて、私は次のことに気づきました：

  • アルゴリズムはどこにでもある： たとえ単純なドキュメント解析であっても、底にあるロジックは木のトラバーサルです。
  • スタックは魔法の道具： 「後入れ先出し」と「二次プッシュ」を理解すれば、ループを使って複雑な再帰問題を解決できます。
  • 技術はつながっている： 実務的な問題（XMLからCSVへ）を解決する思考回路が、なんとLeetCodeのHardモードの面接問題を瞬殺する武器になるのです。

初心者の皆さんへ。「深さ優先探索」のような大層な名前に怯えないでください。木を描いて、迷路にいる自分を想像し、手に皿の山（スタック）を持ってみてください。そうすれば、これらすべてが実は私たちの直感に驚くほど合致していることに気づくはずです。