グラフの探索と迷路

グラフの探索

• グラフの各頂点や辺を二回以上調べることなく，しかも必ず一回は調べる手順
• 単純に考えれば，全部の頂点を番号順に調べればいい
• けど，それはグラフの構造をガン無視しているので，グラフの構造に関係のない計算にしか使えない
• グラフの構造自体を考慮した手順の方が応用が効く

深さ優先探索

• 分かれ道に遭遇したときに，「いけるところまで行ってから引き返そう」という立場を取るのが深さ優先探索
• 分かれ道に来たら，行かなかった道をスタックに記録しておくことで深さ優先探索は実現できる

幅優先探索

• 分かれ道に遭遇したときに，「とりあえず全部の分かれ道にちょっとだけ首突っ込んでみる」という立場を取るのが幅優先探索
• 分かれ道に来たら，行き先候補をキューに突っ込んでおくことで幅優先探索が実現できる

迷路を解く

• 迷路を与えられて，ゴールすることができるかとかゴールするまでの手数はいくらかとかを計算しろという問題はグラフ探索の要領で解くことができる
• 迷路では全探索することよりもゴールに到達することが求められるので，幅優先探索の方が有利
• 幅優先探索では，（もしかしたらゴールするかもしれない）いろんな経路に手を付けるので，より少ない手間でゴールに到達する可能性が高まる
• 深さ優先探索だと，絶対にゴールしない経路に入ってしまったら，行き止まりに遭遇するまで（絶対にゴールすることないのに）突き進んでしまうので不利

迷路

7 8       // 行数 列数
2 2       // スタートの座標
4 5       // ゴールの座標
########  // `#`は壁，`.`は道 
#......#
#.######
#..#...#
#..##..#
##.....#
########

深さ優先探索

• スタックに分かれ道を記録しておく

package main

import (
    "fmt"
)

type pos struct {
    x int
    y int
}

func dfs(maze []string, start, goal pos) int {
    row := len(maze)
    col := len(maze[0])

    dist := make([][]int, row)
    for i := 0; i < row; i++ {
        dist[i] = make([]int, col)
        for j := 0; j < col; j++ {
            dist[i][j] = -1
        }
    }

    q := make([]pos, 0)
    dist[start.y][start.x] = 0
    q = append(q, start)

    for len(q) > 0 {
        p := q[len(q)-1]
        q = q[:len(q)-1]

        for _, d := range []pos{{-1, 0}, {1, 0}, {0, -1}, {0, 1}} {
            y := p.y + d.y
            x := p.x + d.x
            if 0 <= y && y < row && 0 <= x && x < col && dist[y][x] == -1 && string(maze[y][x]) == "." {
                dist[y][x] = dist[p.y][p.x] + 1
                q = append(q, pos{x, y})
            }
        }
    }

    return dist[goal.y][goal.x]
}

func main() {
    var R, C int
    fmt.Scan(&R, &C)

    var start, goal pos
    fmt.Scan(&start.y, &start.x)
    fmt.Scan(&goal.y, &goal.x)
    start.x--
    start.y--
    goal.x--
    goal.y--

    maze := make([]string, R)

    for i := 0; i < R; i++ {
        fmt.Scan(&maze[i])
    }

    fmt.Println(wfs(maze, start, goal))
}

幅優先探索

• キューに分かれ道を記録しておく

package main

import (
    "fmt"
)

type pos struct {
    x int
    y int
}

func wfs(maze []string, start, goal pos) int {
    row := len(maze)
    col := len(maze[0])

    dist := make([][]int, row)
    for i := 0; i < row; i++ {
        dist[i] = make([]int, col)
        for j := 0; j < col; j++ {
            dist[i][j] = -1
        }
    }

    q := make([]pos, 0)
    dist[start.y][start.x] = 0
    q = append(q, start)

    for len(q) > 0 {
        p := q[0]
        q = q[1:]

        for _, d := range []pos{{-1, 0}, {1, 0}, {0, -1}, {0, 1}} {
            y := p.y + d.y
            x := p.x + d.x
            if 0 <= y && y < row && 0 <= x && x < col && dist[y][x] == -1 && string(maze[y][x]) == "." {
                dist[y][x] = dist[p.y][p.x] + 1
                q = append(q, pos{x, y})
            }
        }
    }

    return dist[goal.y][goal.x]
}

func main() {
    var R, C int
    fmt.Scan(&R, &C)

    var start, goal pos
    fmt.Scan(&start.y, &start.x)
    fmt.Scan(&goal.y, &goal.x)
    start.x--
    start.y--
    goal.x--
    goal.y--

    maze := make([]string, R)

    for i := 0; i < R; i++ {
        fmt.Scan(&maze[i])
    }

    fmt.Println(wfs(maze, start, goal))
}