[AtCorder] 深さ優先探索 問題を解く その1 [Swift]

まえがき

AtCoderは、競技プログラミングにおいて人気のあるプラットフォームの一つです。AtCoderには、初心者から上級者まで、幅広いレベルの問題が用意されています。このような問題を解くことで、アルゴリズムやデータ構造など、コーディングスキルを向上させることができます。

私は、AtCoderで反復的に問題を解くことで、共通するアルゴリズムを理解し、スキルを向上させることを目指しています。この記事では、私がAtCoderで解いた問題の中から、深さ優先探索を使用した問題を取り上げ、その解法や解答を紹介していきます。

なお、私が提供する解説は、正しさを保証するものではありません。あくまでも、私がAtCoderでAC（Accepted）となったコードを使用して、解説を行います。

この記事で扱う問題

• 問題 - ATC001A 深さ優先探索
• 問題 - ABC138D - Ki
• 問題 - ABC075C - Bridge

問題 - ATC001A - 深さ優先探索

• ATC001A 深さ優先探索
• https://atcoder.jp/contests/atc001/tasks/dfs_a

【問題文】

高橋君の住む街は長方形の形をしており、格子状の区画に区切られています。長方形の各辺は東西及び南北に並行です。各区画は道または塀のどちらかであり、高橋君は道を東西南北に移動できますが斜めには移動できません。また、塀の区画は通ることができません。

高橋君が、塀を壊したりすることなく道を通って魚屋にたどり着けるかどうか判定してください。

【入力】

入力は以下の形式で標準入力から与えられる。

H W
C[0,0] C[0,1] ... C[0,W-1]
C[1,0] C[1,1] ... C[1,W-1]
:
C[H-1,0] C[H-1,1] ... C[H-1,W-1]

• 1 行目には、街の南北の長さとして整数 H(1≦H≦500) と東西の長さとして整数 W(1≦W≦500) が空白で区切られて与えられる。
• 2 行目からの H 行には、格子状の街の各区画における状態 C[i, j] (0≦i≦H−1, 0≦j≦W−1) が与えられる。
  • i 行目 j 文字目の文字 C[i, j]はそれぞれ s, g, ., # のいずれかで与えられ、座標 (j, i) が下記のような状態であることを表す。
    • s : その区画が家であることを表す。
    • g : その区画が魚屋であることを表す。
    • . : その区画が道であることを表す。
    • # : その区画が塀であることを表す。
  • 高橋君は家・魚屋・道は通ることができるが、塀は通ることができない。
  • 与えられた街の外を通ることはできない。
  • s と g はそれぞれ 1 つずつ与えられる。

【出力】

塀を 1 回も壊さずに、家から魚屋まで辿り着くことができる場合は Yes、辿りつけない場合は No を標準出力に 1 行で出力せよ。

解説

この問題では、与えられた地図の中で、スタート地点からゴール地点までの道が存在するかを判定する問題です。ただし、地図の中には塀が存在し、塀を壊すことはできません。

この問題を解くには与えられた地図を深さ優先探索で探索し、探索済みの地点を "#" に塗り替えます。
そして、スタート地点からゴール地点までの道が存在するかどうかは、ゴール地点が "#" に塗り替えられているかどうかで判定します。

具体的には、以下のような流れになります。

1. 入力を読み込む。

   • 最初に、標準入力から地図の縦幅と横幅を読み込みます。
   • 次に、縦幅と同じ数だけ、各行の地図を文字列として読み込みます。読み込んだ各行の文字列を、それぞれ一つの文字の配列として、二次元配列に格納します。

2. スタート地点とゴール地点を探す。

   • 二次元配列を縦方向と横方向に走査し、スタート地点とゴール地点の座標を取得します。

3. 深さ優先探索で地図を探索する。

   • スタート地点から深さ優先探索を行い、以下の処理をします。

     • 現在地が街の外か、塀の場合は探索しない。そうでない場合は、現在地を "#" に塗り替え、現在地の上下左右の地点を探索する（再帰処理）。

   • 上述の処理によりスタート地点から到達可能な地点は "#" に塗り替えられます。

4. ゴール地点が到達可能かどうかを判定する。

   • ゴール地点の座標が "#" に塗り替えられている場合、到達可能と判定し、"Yes" を出力します。
   • そうでない場合は、到達不可能と判定し、"No" を出力します。

このようにして、スタート地点からゴール地点までの道が存在するかを判定できます。

解答

import Foundation

/// 街の地図を深さ優先探索で探索し、探索した地図の座標を"#"に塗り替える
/// - Parameters:
///   - c: 地図を表す二次元文字配列。inout修飾子により破壊的変更を行う
///   - x, y: 現在地の座標
func dfs(_ c: inout [[Character]], _ x: Int, _ y: Int) {
    let h = c.count
    let w = c[0].count
    // 現在地が街の外か、塀の場合探索しない
    if x < 0 || x >= w || y < 0 || y >= h || c[y][x] == "#" {
        return
    }
    // 現在の座標を通過済みにする（通過済みの箇所を塀と同様に扱う）
    c[y][x] = "#"
    // 現在地の上下左右の地点を探索（再帰処理）
    dfs(&c, x+1, y)
    dfs(&c, x-1, y)
    dfs(&c, x, y+1)
    dfs(&c, x, y-1)
}

// メイン関数
func main() {
    let hw = readLine()!.split(separator: " ").map { Int($0)! }
    let h = hw[0]
    let w = hw[1]
    var c = [[Character]]()
    for _ in 0..<h {
        // 標準入力から一行ずつ読み込み、各行をCharacter型の配列に変換し、cに追加
        let row = Array(readLine()!)
        c.append(row)
    }
    var start = (0, 0)
    var goal = (0, 0)
    // start地点とgoal地点を探索
    for i in 0..<h {
        for j in 0..<w {
            if c[i][j] == "s" {
                // 二次元配列では(x, y)がc[y][x]と表されることに注意する
                start = (j, i)
            }
            if c[i][j] == "g" {
                goal = (j, i)
            }
        }
    }
    // start地点から深さ優先探索を行う
    dfs(&c, start.0, start.1)
    // goal地点が"#"に塗り替えられていたら、到達可能
    if c[goal.1][goal.0] == "#" {
        print("Yes")
    } else {
        print("No")
    }
}

// メイン関数を実行
main()

問題 - ABC138D - Ki

• ABC138D - Ki
• https://atcoder.jp/contests/abc138/tasks/abc138_d

【問題文】

1 から N までの番号がついた N 個の頂点を持つ根付き木が与えられます。 この木の根は頂点 1 で、i 番目の辺 (1≤i≤N−1) は頂点 ai と頂点 bi を結びます。
各頂点にはカウンターが設置されており、はじめすべての頂点のカウンターの値は 0 です。
これから、以下のような Q 回の操作が行われます。

• 操作 j (1≤j≤Q): 頂点 pj を根とする部分木に含まれるすべての頂点のカウンターの値に xj を足す。

すべての操作のあとの各頂点のカウンターの値を求めてください。

【制約】

• 2≤N≤2×10^5
• 1≤Q≤2×10~5
• 1≤ai<bi≤N
• 1≤pj≤N
• 1≤xj≤10^4
• 与えられるグラフは木である。
• 入力中の値はすべて整数である。

【入力】

入力は以下の形式で標準入力から与えられる。

N Q
a1 b1
:
aN−1 bN−1 
p1 x1 
:
pQ xQ

【出力】

すべての操作のあとの各頂点のカウンターの値を、頂点 1,2,…,N の順に空白区切りで出力せよ。

【入力例1】

4 3
1 2
2 3
2 4
2 10
1 100
3 1

【出力例1】

100 110 111 110

解説

この問題は、与えられた根付き木に対して、Q 個の操作を行った後の各頂点のカウンターの値を求める問題です。各操作は、ある頂点を根とする部分木に含まれるすべての頂点のカウンターの値に x を足すものです。

根付き木の各頂点に対して、その頂点以下の部分木に含まれる全ての頂点のカウンターの合計を計算し、最終的なカウンターの値を求めることで問題を解決できます。

以下の　流れで実装します。

1. 根付き木を作成する。
   • 入力の辺の情報から、各頂点について隣接する頂点を記録した隣接リストを作成することができます。
2. 各頂点の初期カウンターの値を求める。
   • 入力のクエリの情報から、各頂点の初期カウンターの値を取得し、配列countersに格納します。
3. 深さ優先探索（DFS）でカウンターの値を更新する。
   • 再帰的にDFSを行い、各頂点以下の部分木に含まれる全ての頂点のカウンターの合計を計算します。
   • 具体的には、親ノードのカウンターの値を加算して、子ノードに再帰的に処理を行います。
   • この際、処理済みのノードは再度処理しないように、親ノードの情報を用いて判定します。
4. 最終的なカウンターの値を計算する。
   • 各頂点のカウンターの初期値と、その頂点以下の部分木に含まれる全ての頂点のカウンターの合計を計算し、最終的なカウンターの値を求めます。
5. 答えを出力する。
   • 求めた各頂点の最終的なカウンターの値を順に出力します。

このようにして、与えられた根付き木に対して、Q 個の操作を行った後の各頂点のカウンターの値を求めることができます。

※　木構造・部分木・根

木構造は、複数の節点（ノード）とそれらを結ぶ枝（エッジ）からなるグラフで、節点同士の関係は階層的になっています。そのため、ある節点を基準としてその下にある節点の集合を部分木と呼びます。
また、木構造には必ず一つの節点がルート（根）となっており、そのルートからすべての節点に至るパスが存在します。ルートからある節点までのパスに含まれる節点と枝を含めたものが、その節点を根とする部分木となります。
例えば、以下のような木おいて、1が根であり、1を根とする部分木には、1, 2, 3, 4, 5が含まれます。また、3を根とする部分木には、3, 4, 5が含まれます。

  1
 / \
2   3
   / \
  4   5

解答

import Foundation

let nq = readLine()!.split(separator: " ").map{Int($0)!}
let n = nq[0] // 頂点（Node）の数
let q = nq[1] // 命令（Query）の数
// 根付き木の隣接リスト（adjacency list）
var adj = Array(repeating: [Int](), count: n)
// 各頂点の最終的なカウンターの値
var answers = Array(repeating: 0, count: n)
// 各頂点の現在のカウンターの値を計算し、格納
var counters = Array(repeating: 0, count: n)

func dfs(_ node: Int, _ parent: Int) {
    // 現在のノードのカウンタの値を確定
    answers[node] += counters[node]
    for child in adj[node] {
        // 連結するノードを探索
        if child != parent {
            // 親ノード以外は現在のノードを根に持つ部分木なので、現在のノードのカウンターの値を子ノードに加算
            counters[child] += counters[node]
            // 現在のノードを親ノードに、子ノードを深さ優先探索
            dfs(child, node)
        }
    }
}

func main() {
    for _ in 0 ..< n - 1 {
        // 辺（Edge）を取得
        let uv = readLine()!.split(separator: " ").map{Int($0)!}
        // 辺が結ぶ頂点番号を0-indexed の形式に変換
        let u = uv[0] - 1
        let v = uv[1] - 1
        // 辺が結ぶ2つの頂点の間に、双方向の辺を追加
        adj[u].append(v)
        adj[v].append(u)
    }

    for _ in 0 ..< q {
        // 命令（Query）を取得
        let px = readLine()!.split(separator: " ").map{Int($0)!}
        let p = px[0] - 1
        let x = px[1]
        // Query: ノードpを根に持つ部分木のカウンターをx加算する
        counters[p] += x
    }

    // ノード0を親を指定せずに深さ優先探索（親ノードに存在しないノード番号-1を指定）
    dfs(0, -1)

    print(answers[0..<n].map{String($0)}.joined(separator: " "))
}

main()

問題 - ABC075C - Bridge

• ABC075C - Bridge
• https://atcoder.jp/contests/abc075/tasks/abc075_c

【問題文】

自己ループと二重辺を含まない N 頂点 M 辺の無向連結グラフが与えられます。i (1≦i≦M) 番目の辺は頂点 ai と頂点 bi を結びます。
グラフから辺を取り除いたとき、グラフ全体が非連結になるような辺のことを橋と呼びます。
与えられた M 本のうち橋である辺の本数を求めてください。

【ノート】

• 自己ループ とは、ai = bi(1≦i≦M) であるような辺 i のことをいいます。
• 二重辺 とは、ai = aj かつ bi = bj (1≦i<j≦M) であるような辺の組 i, j のことをいいます。
• 無向グラフが 連結 であるとは、グラフの任意の二頂点間に経路が存在することをいいます。

【制約】

• 2≦N≦50
• N−1≦M≦min(N(N−1)⁄2,50)
• 1≦ai<bi≦N
• 与えられるグラフは自己ループと二重辺を含まない。
• 与えられるグラフは連結である。

【入力】

入力は以下の形式で標準入力から与えられる。

N M  
a1  b1
​a2  b2
:  
aM  bM

【出力】

M 本の辺のうち、橋である辺の本数を出力せよ。

解説

この問題は、与えられたグラフから橋の本数を求める問題です。
グラフから辺を取り除いたとき、グラフ全体が非連結になるような辺のことを橋と呼びます。

1. 橋を見つけるには、グラフを深さ優先探索で探索しながら、各頂点についてその頂点を通るDFS木における訪問順(order) と、DFS木からその頂点に戻ってくる際に通った 最小訪問順(low) を求めます。

   • 訪問順は、各頂点を最初に訪問した順番です。
   • 最小訪問順は、その頂点から到達できる頂点の中で最小の訪問順です。

2. 訪問済みの頂点vから、未訪問の頂点uへの辺を見つけたとき、次の処理を行います。

   • u が v の親である場合は、その辺は検証しない。
   • u が v の親でない場合は、以下の処理を行う。
     • u が未訪問である場合、uを現在の頂点vの子として再帰的に探索する。
     • u が訪問済みである場合、v から u への辺が後退辺になることがあるため、最小訪問順を更新する。
     • 橋であるかどうかを判定する。
       • order[v] < low[u] である場合、その辺は橋である。
         • 頂点 v から頂点 u に向かう辺が橋であるためには、後退辺が存在しない必要があります。
         • つまり、頂点 v の訪問順よりも頂点 u に割り当てられた最小訪問順が大きい場合に、辺 (v, u) は橋となります。
       • それ以外の場合、その辺は橋ではない。

3. 探索が終了したら、橋の本数を出力します。

このようにして、各頂点について橋の存在を調べ、橋の本数を求めます。

※ DFS木

DFS木とは、深さ優先探索（Depth First Search）アルゴリズムを用いて、グラフ上の各頂点を訪問した際に生成される木構造です。
深さ優先探索では、ある頂点から始めて、その頂点に隣接する頂点を1つずつ探索します。探索済みの頂点は、探索を行っている頂点の子ノードとしてDFS木に追加されます。同様に、隣接する未探索の頂点について探索を行って、それらの頂点もDFS木に追加していくことで、最終的にDFS木が完成します。
DFS木は、グラフ上の連結成分ごとに生成され、連結成分が複数存在する場合はそれぞれのDFS木が生成されます。また、DFS木には、グラフ上の各辺に対して「木の辺」と「後退辺」が存在することになります。後退辺とは、DFS木上で祖先ノードに向かう辺のことで、木の辺以外は後退辺となります。

※ 後退辺

グラフ探索アルゴリズムにおいて、後退辺とはDFS木上で親から子への辺を除く、DFS木以外の辺のことを指します。つまり、ある頂点を訪れたときに、その頂点からDFS木以外の辺で到達できる頂点を訪問した場合、その辺は後退辺と呼ばれます。後退辺は、サイクルが存在することを示唆する役割を持ちます。

解答

import Foundation

// Infinity=十分に大きい数（10^9）。indexと被らない十分に大きい数を用意
let INF = Int(1e9)

// 隣接リストでグラフを表すための配列
// graph[x]には頂点xと辺で繋がった頂点のリストを格納
var graph: [[Int]] = []

// 深さ優先探索によって求めた、各頂点の訪問順
var order: [Int] = []
// 最小訪問順=currentVertexから深さ優先探索で到達可能な頂点の中で最も小さいorder値
var low: [Int] = []

// 橋の本数
var bridgeCount = 0

// 深さ優先探索による橋の検出
func dfs(_ currentVertex: Int, _ parentVertex: Int, _ visitOrder: Int) {
    order[currentVertex] = visitOrder // 訪問順
    low[currentVertex] = visitOrder // 最小訪問順
    // 頂点currentVertexに隣接する各頂点nextVertexについて探索を行う
    for nextVertex in graph[currentVertex] {
        // nextVertexがcurrentVertexの親である場合はスキップする
        if nextVertex == parentVertex { continue }

        if order[nextVertex] == INF {
            // nextVertexが未訪問である場合
            // nextVertexを現在の頂点の子として再帰的に探索する
            dfs(nextVertex, currentVertex, visitOrder + 1)
            // 最小の訪問順を更新する
            // currentVertexの祖先となる頂点と連結している
            low[currentVertex] = min(low[currentVertex], low[nextVertex])
            // 橋であるかどうかを判定する
            // low[nextVertex]がorder[currentVertex]以下のとき、nextVertexはcurrentVertexの祖先となる頂点と連結しているため橋ではない
            if order[currentVertex] < low[nextVertex] {
                bridgeCount += 1
            }
        } else {
            // nextVertexが訪問済みである場合、最小訪問順を更新する
            low[currentVertex] = min(low[currentVertex], order[nextVertex])
        }
    }
}

// メイン処理
func main() {
    // 入力を読み込む
    let nm = readLine()!.split(separator: " ").map{ Int($0)! }
    let n = nm[0] // 頂点の数
    let m = nm[1] // 辺の数

    // グラフを初期化する
    graph = Array(repeating: [], count: n)
    order = Array(repeating: INF, count: n)
    low = Array(repeating: INF, count: n)

    // グラフの辺を読み込む
    for _ in 0..<m {
        // 辺を取得
        let uv = readLine()!.split(separator: " ").map{ Int($0)! }
        // 辺が結ぶ頂点番号を0-indexed の形式に変換
        let u = uv[0] - 1
        let v = uv[1] - 1
        // 辺が結ぶ2つの頂点の間に、双方向の辺を追加
        graph[u].append(v)
        graph[v].append(u)
    }

    // 頂点1からnまで深さ優先探索により、橋の検出を行う
    for v in 0..<n {
        // 頂点 v の探索順序が未定義であるかどうかを判定(order値がINFであれば未探索)
        if order[v] == INF {
            // dfs(v, -1, 0) により、頂点 v に対して深さ優先探索を行う
            // -1は、頂点vの親が存在しないことを表す(存在しない頂点番号)
            // 0は、頂点vの訪問順として設定
            dfs(v, -1, 0)
        }
    }
    
    // 結果の出力
    print(bridgeCount)
}

main()

あとがき

今回は、私がAtCoderで解いた問題から、深さ優先探索を使用した問題を取り上げ、その解法や解答を紹介しました。

この記事を書くことで、自分自身がアルゴリズムやデータ構造の理解を深め、また、Swiftエンジニアの方々と一緒に成長することができたらと思っています。

競技プログラミングは、ただ単にコードを書くだけでなく、問題を解決するために最適なアルゴリズムやデータ構造を選び出すことが重要です。そのため、競技プログラミングを通して、問題解決力やプログラミングスキルを向上させることができると考えます。

今後も、アルゴリズムやデータ構造を焦点に、AtCoderで解いた問題を記事に書いていきたいと思います。最後まで読んでいただき、ありがとうございました。