Goで深さ優先探索と幅優先探索

深さ優先探索と幅優先探索の概要

例えばニュースアプリでニュース一覧からとあるニュースを探しているとして、探し方は大きく分けて2つある。

（カテゴリタブとかはなくてニュースが羅列していて、そのニュースそれぞれが関連ニュースを複数保持している状態をイメージしてもらえれば良い）

深さ優先探索の概要

1つ目は、一覧にあるニュース記事から1つを選んで見て、その記事が探索している記事でなければそのニュース記事内の関連ニュース記事を1つ選んで見る。

その関連ニュース記事が探索している記事でなければ、さらにそのニュース記事内の関連ニュース記事を1つ選んで見る。

これを繰り返して、関連ニュース記事がなくなれば1つ前に探索した関連ニュース記事の中でまだ探索していない関連ニュース記事を探索する。 これを繰り返すと、一覧にあるニュース記事の全てを探索することができる。

深さ優先探索のイメージ

このように深さ優先探索では、同列にある探索対象よりも探索の深さを優先して探索し、最深部まで探索してから1つ上の階層の同列にある探索対象を探索していく。

幅優先探索の概要

2つ目は、一覧にあるニュース記事から1つを選んで見て、その記事が探索している記事でなければ同列にあるニュース記事一覧からまだ探索していないニュース記事を1つ選んで見る。

これを繰り返して1階層目のニュース記事一覧を一通り探索すると、探索してきたニュース記事の関連ニュース記事を探索する（2階層目）。

まず1つ目に探索したニュース記事の関連ニュース記事を1通り探索する。次に2回目に探索したニュース記事の関連ニュース記事を1通り探索する。 これを繰り返し、ニュース記事全てを探索する。

幅優先探索のイメージ

このように幅優先探索では、同列にある探索対象を優先して、同列にある探索対象を探索し終わってから、1つ階層の下の探索対象を探索していく。

深さ優先探索

先ほどの木構造の図を見て分かるように、各ノードを親として見たときに子ノードを探索する処理が繰り返される。 そのため、これをコードで表現するためには、各ノードそれぞれに着目して、再帰関数を使って探索する処理を書けば良い。

問題

競プロの下記の問題をもとにコードを書いてみる。

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1160&lang=ja

標準入力が与えられて島がいくつあるかを判定すれば良い。これは隣接している島を探索していって1セットとしてカウントして行けば良い。各区画ごとに注目して隣接している区画を探索してカウントしていけば良いので、深さ優先で探索していく。

解答

package main

import (
    "fmt"
)

func main() {
    data := make([][][]int, 0) // データセット
    for {
        var w, h int
        fmt.Scan(&w, &h)
        if w == 0 && h == 0 {
            break
        }
        cc := make([][]int, h) // 1つのデータ
        for i := 0; i < h; i++ {
            c := make([]int, w)
            for j := 0; j < w; j++ {
                fmt.Scan(&c[j])
            }
            cc[i] = c
        }
        data = append(data, cc)
    }

    dataSetLen := len(data)
    countList := make([]int, dataSetLen)
    for i := 0; i < dataSetLen; i++ { // 各データセットについて
        w := len(data[i][0])
        h := len(data[i])

        visited := make([][]bool, h) // 探索済みかどうかを格納する二重配列
        for l := 0; l < h; l++ {
            visited[l] = make([]bool, w)
        }

        var count int
        for x := 0; x < w; x++ { // 全ての座標を探索
            for y := 0; y < h; y++ {
                // 座標(x,y)を起点にする島を探索して、探索した座標はvisitedにマーク
                isIsland := dfs(data[i], visited, x, y, w, h)
                if isIsland {
                    count++
                }
            }
        }
        countList[i] = count
    }

    for i := 0; i < len(data); i++ {
        fmt.Println(countList[i])
    }
}

func dfs(cc [][]int, visited [][]bool, baseX, baseY, w, h int) bool {
    if visited[baseY][baseX] == true { // 探索済みの場合
        return false
    }
    visited[baseY][baseX] = true

    if cc[baseY][baseX] != 1 { // 陸じゃない場合
        return false
    }

    // 8方向に移動
    for dx := -1; dx <= 1; dx++ {
        for dy := -1; dy <= 1; dy++ {
            x := baseX + dx
            y := baseY + dy
            if x >= 0 && x < w && y >= 0 && y < h {
                dfs(cc, visited, x, y, w, h)
            }
        }
    }
    return true
}

まず座標を1つ与えられた時に、隣接する島をvisitedにマークしていく再帰関数を定義する。 呼び出す側では、全ての座標を起点にそれぞれ探索していくが、重複計上を防ぐためにvisitedにマークしている場合はreturnする。 再帰関数がtrueで返ってくるときは島を1つ探索し終わった時なのでカウントをインクリメントする。

ポイント

ポイントは、①探索済みかどうかをマークするための配列を作成すること。②再帰関数で探索した箇所をマークしていくこと。③全ての座標を起点にして再帰関数を呼び出すこと。

幅優先探索

先ほどの木構造の図を見て分かるように、順番に各ノードを見ていくと同時に探索したノードは保存しておく必要がある。

これはキューを使えば実現できる。

問題

以下の問題をもとにコードを書いていく。

atcoder.jp

マス目を標準入力で与えられて、最短経路でゴールまで行くまでの手数を数え上げられれば良い。

解答

package main

import "fmt"

func main() {
    var H, W int
    fmt.Scan(&H, &W)
    c := make([]string, H)
    visited := make([][]int, H) // 対象とする座標に行き着くまでのcostを入れる二重配列
    for i := 0; i < H; i++ {
        var s string
        fmt.Scan(&s)
        c[i] = s
        visited[i] = make([]int, W)
    }

    if string(c[0][0]) == "#" || string(c[H-1][W-1]) == "#" {
        fmt.Println(-1)
        return
    }

    var q queue
    q.push(coordinate{
        x: 1,
        y: 1,
    })

    // 配列を-1で初期化
    for i := 0; i < H; i++ {
        for j := 0; j < W; j++ {
            visited[i][j] = -1
        }
    }
    visited[0][0] = 0 // スタートはcostは0

    dxList := []coordinate{
        {
            x: 1,
            y: 0,
        },
        {
            x: 0,
            y: 1,
        },
        {
            x: -1,
            y: 0,
        },
        {
            x: 0,
            y: -1,
        },
    }

    for len(q.slice) > 0 {
        cBefore := q.pop()
        for i := 0; i < 4; i++ {
            nextX := cBefore.x + dxList[i].x
            nextY := cBefore.y + dxList[i].y
            if 1 <= nextX && nextX <= W && 1 <= nextY && nextY <= H {
                xIndex := nextX - 1
                yIndex := nextY - 1
                if string(c[yIndex][xIndex]) == "." && visited[yIndex][xIndex] == -1 {
                    visited[yIndex][xIndex] = visited[cBefore.y-1][cBefore.x-1] + 1
                    q.push(coordinate{
                        x: nextX,
                        y: nextY,
                    })
                }
            }
        }
    }

    if visited[H-1][W-1] == -1 {
        fmt.Println(-1)
        return
    }

    var whiteCount int // 初期配置の白の数
    for i := 0; i < H; i++ {
        for j := 0; j < W; j++ {
            if string(c[i][j]) == "." {
                whiteCount++
            }
        }
    }

    minRouteWhiteCount := visited[H-1][W-1] + 1  // ゴールするための最短経路で使う白の数
    fmt.Println(whiteCount - minRouteWhiteCount) // 初めにあった白の数から必要な分を引いた不要な白の数
}

type coordinate struct {
    x int
    y int
}

type queue struct {
    slice []coordinate
}

func (q *queue) push(c coordinate) {
    q.slice = append(q.slice, c)
}

func (q *queue) pop() coordinate {
    c := q.slice[0]
    q.slice = q.slice[1:]
    return c
}

最短経路でゴールまで行くのに必要なコストが必要なので、今回は各区画までに到達するのに必要な最低コストを記録する二重配列を用意する。 スタートはコスト0で到達できることが自明なので、スタートの座標をキューに入れ、最短コストをvisitedに記録する。

スタートから探索していき、そこから+1のコストで探索できる座標を探して、既に最低コストで探索されていない場合は最短コストをvisitedに記録して、キューに入れておく。後ほどキューに入れたこの座標を基準にまたコスト+1で探索できる座標を探す。つまり、キューに値がある限りはループを回す。

こうして最短コストを記録していくと、ゴールを含む各座標にはそこに至るまでの最短コストが記録されている。最短ルートを辿るには、ゴールまでの最短コストからデクリメントして辿れる経路を辿れば良い。

ポイント

ポイントは、探索にかかるコストは1つ前の座標を探索するのにかかるコスト+1であること。②visitedには最低コストを記録するので、visitedが初期値（今回でいう-1）であればコストを記録するが、初期値以外の値が入っていれば、その値がその区画に到達するための最短コストなので記録をしないこと。