深さ優先探索について勉強する

前に競プロの勉強したときから、引き続きatcoderをこっそり続けてます。

www.nogawanogawa.work

2020年は、なんとか年内に茶色になることができました。

今回は、競プロをやっていると非常に多く遭遇する深さ優先探索というものについて、勉強してみたのでそのメモです。

深さ優先探索

深さ優先探索は、木やグラフを探索を行う際のアルゴリズムで、探索対象となる木やグラフの最初のノードから、目的のノードが見つかるか子のないノードに行き着くまで深く伸びていく探索です。

ja.wikipedia.org

詳しい解説は、こちらの記事が非常にわかりやすいので、こちらをご参照ください。

qiita.com

qiita.com

例題を試しに解いてみる

習うより慣れろ、ってことで例題をいくつか解いてみて感じを掴んでいきたいと思います。

グリッドグラフに関する問題

atcoder.jp

この問題は、解説にある通り、塗りつぶしで解いてみます。 やり方は単純に、一度通ったマスに印をつけながらいけるところまで進み、最後にゴールに到達できていたらYes、そうでなければNoと表示すればできます。

コード

package main

import (
    "fmt"
    "strings"
)

func dfs(c [][]string, d [][]bool, i int, j int, H int, W int){
    
    d[i][j] = true

    var next_i, next_j int

    next_i = i-1
    next_j = j
    if next_i >= 0{
        if (d[next_i][next_j] == false) && (c[next_i][next_j] != "#"){
            dfs(c, d, next_i, next_j, H, W)
        }    
    }
    
    next_i = i+1
    next_j = j
    if next_i < H{
        if (d[next_i][next_j] == false) && (c[next_i][next_j] != "#"){
            dfs(c, d, next_i, next_j, H, W)
        }
    }

    next_i = i
    next_j = j-1
    if next_j >= 0{
        if (d[next_i][next_j] == false) && (c[next_i][next_j] != "#"){
            dfs(c, d, next_i, next_j, H, W)
        }
    }

    next_i = i
    next_j = j+1
    if next_j < W{
        if (d[next_i][next_j] == false) && (c[next_i][next_j] != "#"){
            dfs(c, d, next_i, next_j, H, W)
        }
    }
    return
}

func main() {
    var H, W int
    fmt.Scanf("%d %d", &H, &W)

    d := make([][]bool, H)
    c := make([][]string, H)
    for i:=0; i<H; i++{
        c[i] = make([]string, W)
        d[i] = make([]bool, W)
    }


    var start_i, start_j, goal_i, goal_j int
    var row string 
    for i:=0; i<H; i++{

        fmt.Scanf("%s", &row)
        rows := strings.Split(row, "") 

        for j:=0; j<W; j++{
            c[i][j] = rows[j]
            if c[i][j] == "s"{
                start_i = i
                start_j = j
            }
            if c[i][j] == "g"{
                goal_i = i
                goal_j = j
            }
        }
    }

    dfs(c, d, start_i, start_j, H, W)

    if d[goal_i][goal_j]{
        fmt.Printf("Yes\n")
    } else{
        fmt.Printf("No\n")
    }
}

グリッドグラフに関する問題（その2）

atcoder.jp

こちらの問題は、海の部分を一つ選択して、そこから深さ優先探索を行ったときに、すべての陸地にたどり着けるかを判定することで解くことができます。

コード

package main
 
import (
  "fmt"
  "strings"
)
 
func dfs(B [][]string, i int, j int){

  B[i][j] = "x"

  var next_i, next_j int

  next_i = i-1
  next_j = j
  if next_i >= 0{
      if B[next_i][next_j] == "o"{
        dfs(B, next_i, next_j)
      }    
  }
  
  next_i = i+1
  next_j = j
  if next_i < 10{
    if B[next_i][next_j] == "o"{
      dfs(B, next_i, next_j)
    }    
  }

  next_i = i
  next_j = j-1
  if next_j >= 0{
    if B[next_i][next_j] == "o"{
      dfs(B, next_i, next_j)
    }    
  }

  next_i = i
  next_j = j+1
  if next_j < 10{
    if B[next_i][next_j] == "o"{
      dfs(B, next_i, next_j)
    }    
  }
  return

}

func main() {

  A := make([][]string, 10)
  B := make([][]string, 10)
  for i := 0; i < 10; i++ {
    A[i] = make([]string, 10)
    B[i] = make([]string, 10)
  }

  var row string
  for i := 0; i < 10; i++ {
    fmt.Scanf("%s", &row)
    rows := strings.Split(row, "")

    for j:= 0; j < 10; j++ {
      A[i][j] = rows[j]     
    }
  }

  var flag bool
  for i := 0; i < 10; i++ {
    for j:= 0; j < 10; j++ {
      if A[i][j] == "x"{
        flag = true
        for k := 0; k < 10; k++ {
          _ = copy(B[k], A[k])        
        }

        dfs(B, i, j)

        // 確認
        for k := 0; k < 10; k++ {
          for l:= 0; l < 10; l++ {
            if B[k][l] == "o"{
              flag = false
              break
            }
          }
          if flag == false{
            break
          }
        }
        if flag == true {
          fmt.Printf("YES\n")    
          return
        }
      }
    }
  }

  fmt.Printf("NO\n")
}

二部グラフ判定

atcoder.jp

こちらはグラフの色つけの問題です。 探索の始点は勝手に決めれるので、グラフ構造を整えてあげて適当な点からグラフを探索しながら辺の長さを考慮しながら色付してあげればできます。

コード

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)

type Node struct {
    next []int64
    edge []int64
    color int
}

func dfs(x []Node, j int64){

    nexts := x[j].next
    edges := x[j].edge
 
    for i:=0; i<len(nexts); i++{
        next := nexts[i]
        edge := edges[i]

        if x[next].color == -1 {
            if edge % 2 == 0{
                if x[j].color == 0{
                    x[next].color = 0
                } else {
                    x[next].color = 1
                }
            } else {
                if x[j].color == 0{
                    x[next].color = 1
                } else {
                    x[next].color = 0
                }
            }
            dfs(x, next)
        }
    }
}

var sc = bufio.NewScanner(os.Stdin)

func nextInt() int64 {
    sc.Scan()
    i, e := strconv.ParseInt(sc.Text(),10,64)
    if e != nil {
        panic(e)
    }
    return i
}

func main() {
    sc.Split(bufio.ScanWords)
    var N int64
    fmt.Scanf("%d", &N)

    u := make([]int64, N-1)
    v := make([]int64, N-1)
    w := make([]int64, N-1)

    var i int64
    for i=0; i<N-1; i++{
        u[i] = nextInt()
        v[i] = nextInt()
        w[i] = nextInt()
    }

    x := make([]Node, N+1)
    for i=2; i<N+1; i++{
        x[i].color = -1
    }
    for i=0; i<N-1; i++{
        x[u[i]].next = append(x[u[i]].next, v[i])
        x[u[i]].edge = append(x[u[i]].edge, w[i])

        x[v[i]].next = append(x[v[i]].next, u[i])
        x[v[i]].edge = append(x[v[i]].edge, w[i])
    }

    dfs(x, 1)

    for i=1; i<N+1; i++{
        fmt.Printf("%d\n", x[i].color)
    }
}

二部グラフ（その2）

atcoder.jp

上と同じでグラフの色つけ問題です。

コード

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)

type Node struct {
    next  []int
    color int
}

func contains(s []int, e int) bool {
    for _, v := range s {
        if e == v {
            return true
        }
    }
    return false
}

func dfs(nodes []Node, before []int, count int, start int) {

    now := nodes[start]
    if count%2 == 0 {
        nodes[start].color = 0
    } else {
        nodes[start].color = 1
    }

    for i := 0; i < len(now.next); i++ {
        if contains(before, now.next[i]) == false {
            var before_ []int
            copy(before_, before)
            before_ = append(before_, start)
            dfs(nodes, before_, count+1, now.next[i])
        }
    }
}

var sc = bufio.NewScanner(os.Stdin)

func nextInt() int {
    sc.Scan()
    i, e := strconv.ParseInt(sc.Text(), 10, 64)
    if e != nil {
        panic(e)
    }
    return int(i)
}

func main() {

    sc.Split(bufio.ScanWords)

    var N, Q int
    fmt.Scanf("%d %d", &N, &Q)

    nodes := make([]Node, N)

    var a, b int
    for i := 0; i < N-1; i++ {
        a = nextInt() - 1
        b = nextInt() - 1
        nodes[a].next = append(nodes[a].next, b)
        nodes[b].next = append(nodes[b].next, a)
    }

    C := make([]int, Q)
    D := make([]int, Q)
    for i := 0; i < Q; i++ {
        C[i] = nextInt() - 1
        D[i] = nextInt() - 1
    }

    var before []int
    dfs(nodes, before, 0, 0)

    for i := 0; i < Q; i++ {
        x := nodes[C[i]].color
        y := nodes[D[i]].color
        if x == y {
            fmt.Printf("Town\n")
        } else {
            fmt.Printf("Road\n")
        }
    }
}

参考文献

今回はこちらの文献を参考にさせていただきました。

問題解決力を鍛える！アルゴリズムとデータ構造 (ＫＳ情報科学専門書)

qiita.com

qiita.com

感想

緑コーダーになるためには、DFS・BFSは避けては通れないと思い、勉強してみました。 日頃の精進も大事ですが、たまにはこうやって特定のテーマを体系的に勉強してみることも重要かなと思いやってみました。

また別のテーマを勉強するときにまとめていきたいと思います。