どこにでもいるSEの備忘録

たぶん動くと思うからリリースしようぜ

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

前に競プロの勉強したときから、引き続き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)
    }
}

参考文献

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

qiita.com

qiita.com

感想

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

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