3
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

GoでDFSを書く(ABC161 D - Lunlun Numberを解く)

Last updated at Posted at 2020-05-07

はじめに

唐突ですがGoで競プロコードはどう書くのかなと気になったのでやります.
Goが好きなので.
競プロ経験者だけれどGoは知らない人がこの記事を読んで「Goってこんな感じなんだ~」って流し見してくれれば嬉しいです.

注意

ぼく自身,競技プログラミングは弱く,かつ普段はC++を使っているので最適でなく助長な記述等になっているかもしれませんがご容赦ください.あくまで雰囲気を感じてもらえたらとおもいます.ちなみにこの問題が初めてのGoでのACになりました.また,DFS自体についての解説,問題の解説は行っていません.

#やる
問題はABC161D - Lunlun Numberを解きます.
この問題の選定理由は特にないです.ここ最近でDFS使って解けるからって所でしょうか(ABC165-Cがありますが...)
早速ですが解答コードを先に見せてから解説(?)していこうと思います.

package main

import (
	"fmt"
	"sort"
)

var ans []int

func dfs(n int) {
	if 3234566667 < n {
		return
	}
	ans = append(ans, n)
	d := n % 10
	if d != 0 {
		dfs(n*10 + d - 1)
	}
	if d != 9 {
		dfs(n*10 + d + 1)
	}
	dfs(n*10 + d)
}

func main() {
	var k int
	fmt.Scan(&k)
	for i := 0; i < 9; i++ {
		dfs(i + 1)
	}
	sort.Ints(ans)
	fmt.Println(ans[k-1])
}

意外と普通ですね(?)

package

package main

import (
    "fmt"
    "sort"
)

まずは必要パッケージをインポートします.

  • fmt : 標準入出力を使うために用います.
    fmt.Scan(&n)で変数nの標準入力を受け付けます.
    fmt.Printf("%d\n",n)で変数nを出力します.さらにfmt.Println(n)で改行付きで標準出力します.ここまでは競プロerお馴染みのC++と差異はありません.パッケージから用いる関数の頭文字を大文字にすることを忘れないようにしましょう.

  • sort : その名の通りソートの為のパッケージです.配列やスライスはもちろんmapなどにも対応しています.

slice

var ans []int

C++で言うところのvectorで可変長配列です.ここに解候補を入れていきます.
型の宣言は変数名の後に書くことに気を付けます.

DFS

func dfs(n int) {
	if 3234566667 < n {
		return
	}
	ans = append(ans, n)
	d := n % 10
	if d != 0 {
		dfs(n*10 + d - 1)
	}
	if d != 9 {
		dfs(n*10 + d + 1)
	}
	dfs(n*10 + d)
}
  • ここがメインとなるDFSです.Goでの関数の書き方は
func 関数名(引数 型) 戻り値型{
     処理
}

のように書きます.今回のDFSは整数nを引数にして,戻り値はありません(C++でいうvoid型です)Goのint型は実装のCPUやOSに依存し,int64型かint32型になるみたいです.

  • sliceへの要素の追加はappendを使います.ここで注意するべきなのは
append(ans,n)

ではなく

ans=append(ans,n)

と書くことに気を付けましょう.

  • Goでのif文は処理部分には1行の処理でも必ず中括弧{}を用います.

  • 再帰の書き方もそのままで分かりやすいですね.

main関数

func main() {
	var k int
	fmt.Scan(&k)
	for i := 0; i < 9; i++ {
		dfs(i + 1)
	}
	sort.Ints(ans)
	fmt.Println(ans[k-1])
}

main関数から処理がスタートします.ですので標準入力や具体的な処理,解答の出力はmain関数で行います.
今回の問題では特筆すべきことは無いですが,for文の書き方もC++と同様で分かりやすいですね.

おわりに

初めてGoで競プロの問題を解きましたが,特に困ることもなく書きやすかったです.
今回突発的に本記事の作成をしたため,問題選定が微妙だったかもしれません.(扱う内容的にはstringやデータ構造の利用も無く単なる整数の処理でした)
これを機に僕もGoで問題を解いていきたいと思います.Goでの競プロを取り組む人が増えていったらいいなと思います(^^)/.

3
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
3
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?