Zenn
Rabee Tech blogPublicationへの投稿
🔄

再帰関数をループに書き換えるメモ(DFS, BFS)(JavaScript, Golang)

simiraaaa
2023/05/09に公開
Go
JavaScript
AtCoder
algorithm
tech

目的

  1. スタックオーバーフロー (js だと Maximum call stack size exceeded) を回避するため
  2. 関数定義が面倒な言語でわざわざ関数を定義したくない

2はそこまで重要ではなく、主に1を解決することが目的です。

https://algo-logic.info/dfs/
https://algo-logic.info/bfs/
https://algo-logic.info/brute-force-dfs/
↑こちらの記事を参考に AtCoder ABC114 C - 755 の問題を例に書きます。

アルゴリズムの説明

問題文を要約すると

  • 入力: 最大10^9の数値Nが与えられる
  • 出力: N以下で3,5,7をすべて含む数がいくつあるかを出力

それをどのようなロジックで解くかというと

3, 5, 7を順番にループして文字列としてどんどん足してチェックしていくといった感じです。

イメージ
  • 3
    • 33
      • 333
      • 533
      • 733
    • 53
      • 353
      • 553
      • 753
    • 73
      • 373
      • 573
      • 773
  • 5
    • 35
      • ...

DFS(深さ優先探索)を再帰処理で書いた場合

DFS の探索順

DFSではこの順番で探索されます。

DFS の探索順(N=1000)
3
33
333
533
733
53
353
553
753
73
373
573
773
5
35
335
535
735
55
355
555
755
75
375
575
775
7
37
337
537
737
57
357
557
757
77
377
577
777

go

長いので主要な処理以外は省いています。


func solve() {
	N := readInt()
	str357 := []string{"3", "5", "7"}
	ans := 0
	var dfs func(s string)
	dfs = func(s string) {
		// 最初(空文字)のときはループする
		if s != "" {
			n := atoi(s)
			if n > N {
				return
			}
			// 3, 5, 7 をすべて含むか
			f := true
			for _, v := range str357 {
				if !strings.Contains(s, v) {
					f = false
				}
			}
			if f {
				ans++
			}
			// log(n)
		}
		for _, v := range str357 {
			dfs(v + s)
		}
	}
	dfs("")
	log(ans)
}
go dfs 全文
//go:build ignore

package main

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

func solve() {
	N := readInt()
	str357 := []string{"3", "5", "7"}
	ans := 0
	var dfs func(s string)
	dfs = func(s string) {
		// 最初(空文字)のときはチェック処理をスルーする
		if s != "" {
			n := atoi(s)
			if n > N {
				return
			}
			// 3, 5, 7 をすべて含むか
			f := true
			for _, v := range str357 {
				if !strings.Contains(s, v) {
					f = false
				}
			}
			if f {
				ans++
			}
			// log(n)
		}
		for _, v := range str357 {
			dfs(v + s)
		}
	}
	dfs("")
	log(ans)
}

func main() {
	sc.Buffer([]byte{}, math.MaxInt32)
	sc.Split(bufio.ScanWords)
	defer wr.Flush()
	solve()
}

var sc = bufio.NewScanner(os.Stdin)
var wr = bufio.NewWriter(os.Stdout)

func log(v ...interface{}) {
	fmt.Fprintln(wr, v...)
}

func read() string {
	sc.Scan()
	return sc.Text()
}

func readInt() int {
	sc.Scan()
	i, _ := strconv.Atoi(sc.Text())
	return i
}

func atoi(s string) int {
	i, _ := strconv.Atoi(s)
	return i
}

js


const input = require("fs").readFileSync("/dev/stdin", "utf8").split(/ |\n/);
const N = Number(input[0]);
const str357 = ['3', '5', '7'];
let ans = 0;

const dfs = (s) => {
  // 最初(空文字)のときはチェック処理をスルーする
  if (s !== '') {
    const n = Number(s);
    if (n > N) return;
    // 3, 5, 7 をすべて含むか
    if (str357.every(v => s.includes(v))) ans++;
    // console.log(n);
  }
  str357.forEach(v => dfs(v + s));
};

dfs('');
console.log(ans);

DFS(深さ優先探索)をループ処理に書き換えた場合

Stackを使ってループ処理をしていきます。
Stackに積むのは、 再帰関数の引数になるもの と考えると覚えやすいです。

注意点として、同じDFSでもStackに積む順序によっては、再帰関数と処理順が変わってしまうため、実行順が重要な場合は、再帰呼び出しの逆順にループして積んでいくように注意してください。

結果的には、全範囲探索されるため順番を気にする必要がない場合は、ループ順は適当で問題ありません。

go


func solve() {
	N := readInt()
	str357 := []string{"3", "5", "7"}
	ans := 0
	stack := []string{""}
	for len(stack) > 0 {
		s := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		if s != "" {
			n := atoi(s)
			if n > N {
				continue
			}
			// 3, 5, 7 をすべて含むか
			f := true
			for _, v := range str357 {
				if !strings.Contains(s, v) {
					f = false
				}
			}
			if f {
				ans++
			}
			// log(n)
		}
		for _, v := range str357 {
			stack = append(stack, v+s)
		}
		// 実行順を再帰関数と同じにする場合は逆ループ
		// for i := len(str357) - 1; i >= 0; i-- {
		// 	stack = append(stack, str357[i]+s)
		// }
	}
	log(ans)
}
go DFS ループ 全文
//go:build ignore

package main

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

func solve() {
	N := readInt()
	str357 := []string{"3", "5", "7"}
	ans := 0
	stack := []string{""}
	for len(stack) > 0 {
		s := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		if s != "" {
			n := atoi(s)
			if n > N {
				continue
			}
			// 3, 5, 7 をすべて含むか
			f := true
			for _, v := range str357 {
				if !strings.Contains(s, v) {
					f = false
				}
			}
			if f {
				ans++
			}
			// log(n)
		}
		for _, v := range str357 {
			stack = append(stack, v+s)
		}
		// 実行順を再帰関数と同じにする場合は逆ループ
		// for i := len(str357) - 1; i >= 0; i-- {
		// 	stack = append(stack, str357[i]+s)
		// }
	}
	log(ans)
}

func main() {
	sc.Buffer([]byte{}, math.MaxInt32)
	sc.Split(bufio.ScanWords)
	defer wr.Flush()
	solve()
}

var sc = bufio.NewScanner(os.Stdin)
var wr = bufio.NewWriter(os.Stdout)

func log(v ...interface{}) {
	fmt.Fprintln(wr, v...)
}

func read() string {
	sc.Scan()
	return sc.Text()
}

func readInt() int {
	sc.Scan()
	i, _ := strconv.Atoi(sc.Text())
	return i
}

func atoi(s string) int {
	i, _ := strconv.Atoi(s)
	return i
}

js

const input = require("fs").readFileSync("/dev/stdin", "utf8").split(/ |\n/);
const N = Number(input[0]);
const str357 = ['3', '5', '7'];
let ans = 0;

const stack = [''];

while (stack.length) {
  const s = stack.pop();
  // 最初(空文字)のときはチェック処理をスルーする
  if (s !== '') {
    const n = Number(s);
    if (n > N) continue;
    // 3, 5, 7 をすべて含むか
    if (str357.every(v => s.includes(v))) ans++;
    // console.log(n);
  }
  str357.forEach(v => stack.push(v + s));
}

console.log(ans);

BFS(幅優先探索)を再帰処理で書いた場合?

書こうと思ったのですが、書き方がわからない上に再帰でやるメリットがなさそうなので割愛します。

BFS(幅優先探索)をループ処理で書いた場合

これは、DFSのループパターンができたら、そのStackをQueueに変えるだけでできます。
ただし、一つ問題点があり、jsではarray.shiftが遅いので、arrayでqueueを実装しないほうが良いです。

BFS の探索順(N=1000)

BFSの探索順
3
5
7
33
53
73
35
55
75
37
57
77
333
533
733
353
553
753
373
573
773
335
535
735
355
555
755
375
575
775
337
537
737
357
557
757
377
577
777

go


func solve() {
	N := readInt()
	str357 := []string{"3", "5", "7"}
	ans := 0
	queue := []string{""}
	for len(queue) > 0 {
		s := queue[0]
		queue = queue[1:]
		if s != "" {
			n := atoi(s)
			if n > N {
				continue
			}
			// 3, 5, 7 をすべて含むか
			f := true
			for _, v := range str357 {
				if !strings.Contains(s, v) {
					f = false
				}
			}
			if f {
				ans++
			}
			// log(n)
		}
		for _, v := range str357 {
			queue = append(queue, v+s)
		}
	}
	log(ans)
}
go BFS 全文
//go:build ignore

package main

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

func solve() {
	N := readInt()
	str357 := []string{"3", "5", "7"}
	ans := 0
	queue := []string{""}
	for len(queue) > 0 {
		s := queue[0]
		queue = queue[1:]
		if s != "" {
			n := atoi(s)
			if n > N {
				continue
			}
			// 3, 5, 7 をすべて含むか
			f := true
			for _, v := range str357 {
				if !strings.Contains(s, v) {
					f = false
				}
			}
			if f {
				ans++
			}
			// log(n)
		}
		for _, v := range str357 {
			queue = append(queue, v+s)
		}
	}
	log(ans)
}

func main() {
	sc.Buffer([]byte{}, math.MaxInt32)
	sc.Split(bufio.ScanWords)
	defer wr.Flush()
	solve()
}

var sc = bufio.NewScanner(os.Stdin)
var wr = bufio.NewWriter(os.Stdout)

func log(v ...interface{}) {
	fmt.Fprintln(wr, v...)
}

func read() string {
	sc.Scan()
	return sc.Text()
}

func readInt() int {
	sc.Scan()
	i, _ := strconv.Atoi(sc.Text())
	return i
}

func atoi(s string) int {
	i, _ := strconv.Atoi(s)
	return i
}

js


// 雑な Queue を実装
const newQueue = (initial_values) => {
  const newQueueNode = (value, next) => ({ value, next });
  const queue = {
    first: null,
    last: null,
    size: 0,
    enqueue(value) {
      const q = newQueueNode(value);
      if (!this.first) {
        this.first = q;
      } else {
        this.last.next = q;
      }
      this.last = q;
      return ++this.size;
    },
    dequeue() {
      if (!this.first) return null;
      const q = this.first;
      this.first = q.next;
      this.size--;
      if (this.size <= 0) {
        this.first = null;
        this.last = null;
      }
      return q.value;
    },
  };
  if (Array.isArray(initial_values)) {
    initial_values.forEach(v => queue.enqueue(v));
  }
  return queue;
};

const input = require("fs").readFileSync("/dev/stdin", "utf8").split(/ |\n/);
const N = Number(input[0]);
const str357 = ['3', '5', '7'];
let ans = 0;

const queue = newQueue(['']);

while (queue.size) {
  const s = queue.dequeue();
  // 最初(空文字)のときはチェック処理をスルーする
  if (s !== '') {
    const n = Number(s);
    if (n > N) continue;
    // 3, 5, 7 をすべて含むか
    if (str357.every(v => s.includes(v))) ans++;
    // console.log(n);
  }
  str357.forEach(v => queue.enqueue(v + s));
}

console.log(ans);

あとがき

DFSとBFSをどう書いたらいいのかすぐに忘れてしまうので、ここを見てすぐに思い出せるようにしたいです。

基本的にはループで覚えておいて、DFSはスタック、BFSはキューと覚えれば良さそうですね。

なにか間違いやアドバイスがありましたらコメントお願いします。

Rabee Tech blog
Rabee Tech blogPublication

Discussion