paiza問題集「拡張ダイクストラ - コストを0にできるチケット」をGo言語で解く
目次
アルゴリズムとGo言語の勉強のためpaizaの「グリッド版ダイクストラ問題セット」を解いていきます。 5番目の問題「拡張ダイクストラ - コストを0にできるチケット」を解きます。
paiza問題へのリンクです。
問題を解く
解き方は「paiza開発日誌」で解説されている通りです。
今まで解答してきたコードを修正して作成しています。
すでに通過した経路を確認する処理では、前回までは座標のみで判定していたのをチケットの使用枚数も付加するようにしています。
/*
これはpaizaラーニングの「グリッド版ダイクストラ問題セット」から
「問題4: 拡張ダイクストラ - コストを0にできるチケット」
https://paiza.jp/works/mondai/grid_dijkstra/grid_dijkstra__d4
にGo言語でチャレンジした試行錯誤コードです。
Go初心者が学習用に作ったコードなので本来は不要な処理があります。
*/
/*
問題の解き方はpaiza開発日誌「最短経路問題で頻出の「ダイクストラ法」とは？練習問題で徹底解説」
https://paiza.hatenablog.com/entry/2020/11/27/150000
の通りです。
構造体 Position 盤面上の位置を表す
関数 func (p *Position) Equal(o *Position) bool ： 2つの位置が同一か判定する
func (p *Position) Plus(o *Position) *Position ： 2つの位置を加算する
構造体 Board 盤面を表す
関数 func NewBoard(h int, w int) *Board ： 盤面を初期作成する
func (b *Board) IsWithinRange(p *Position) bool ： 位置が盤面上か判定する
func (b *Board) GetCost(p Position) int ： 指定位置のコストを返す
func (b *Board) dijkstra(s Position, g Position) error ： 問題を解く この問題のメイン
構造体 Route 通過経路を表す
関数 func NewRoute(p Position, c int) *Route ： 通過経路を新規作成する
func (r *Route) GetKey() int ： 重複判定用の値を返す
PriorityQueue 通過経路の優先度付きキューを定義
go言語の"container/heap"を使用して優先度付きキューを実装
関数 func (pq PriorityQueue) Len() int 通過経路キューの要素数を返す
func (pq PriorityQueue) Less(i, j int) bool ： 優先度付きキューの優先度判定に使用
func (pq PriorityQueue) Swap(i, j int) ： 優先度付きキューの並べ替えに使用
func (pq *PriorityQueue) Push(x interface{}) ： 優先度付きキューにアイテムを追加する
func (pq *PriorityQueue) Pop() interface{} ： 優先度付きキューからアイテムを取り出す
*/
package main
import (
"bufio"
"container/heap"
"errors"
"fmt"
"os"
"strconv"
"strings"
)
///////////////////////////
// ここからPosition構造体定義
// 盤面の位置を表す構造体
type Position struct {
// x は列 0〜W-1
x int
// y は行 0〜H-1
y int
}
// Equal は盤面位置が同じか判定する
func (p *Position) Equal(o *Position) bool {
if o == nil {
return false
} else {
return p.x == o.x && p.y == o.y
}
}
// Plus は盤面位置を加算する ただし、位置の範囲外チェックは行わない
func (p *Position) Plus(o *Position) *Position {
if o == nil {
return nil
}
// 加算した位置を生成し、返す
// ここでは範囲外チェックは行わない
var result Position = Position{x: p.x + o.x, y: p.y + o.y}
return &result
}
// ここまでPosition構造体定義
///////////////////////////
// 盤面上の移動可能方向を定義する 右、上、左、下の4方向
// var定義だが定数のように使うことにする
var MOVABLE_DIRECTION []Position = []Position{
{x: 1, y: 0},
{x: 0, y: -1},
{x: -1, y: 0},
{x: 0, y: 1}}
///////////////////////////////
// ここから通過経路構造体定義
// 通過経路
type Route struct {
// 現在位置
pos Position
// 現在地までのコスト
cost int
// 残りチケット枚数
ticket int
// 現在位置に来る直前にいたルート
ref *Route
// indexはヒープの更新のために使用する
index int
}
// NewRoute は通過経路のコンストラクタ
// i p : 位置
// c : コスト初期値
// t : 残りチケット枚数
// r : 一つ前にいた位置
// o *Route : 初期化した通過経路
func NewRoute(p Position, c int, t int, r *Route) *Route {
var result *Route = new(Route)
result.pos = p
result.cost = c
result.ticket = t
result.ref = r
return result
}
// 重複判定用のキーを返す
func (r *Route) GetKey() int {
// 判定項目には座標と0チケットの枚数を使用する
return r.pos.x<<16 + r.pos.y<<8 + r.ticket
}
// ここまで通過経路構造体定義
///////////////////////////////
///////////////////////////////////
// ここから優先度付きキューの定義
// 通過経路の優先度付きキューを定義
type PriorityQueue []*Route
// 優先度付きキューの要素数を返す
func (pq PriorityQueue) Len() int {
return len(pq)
}
// 優先度を判定するためのLess関数
func (pq PriorityQueue) Less(i, j int) bool {
return pq[i].cost < pq[j].cost
}
// キュー内のアイテム位置を入れ替える
func (pq PriorityQueue) Swap(i, j int) {
pq[i], pq[j] = pq[j], pq[i]
pq[i].index = i
pq[j].index = j
}
// キューにアイテムを追加する
func (pq *PriorityQueue) Push(x interface{}) {
var n int = len(*pq)
var item *Route = x.(*Route)
item.index = n
*pq = append(*pq, item)
}
// キューから先頭のアイテムを取り出し、元の配列から削除する
func (pq *PriorityQueue) Pop() interface{} {
var old PriorityQueue = *pq
var n int = len(old)
var item *Route = old[n-1]
old[n-1] = nil // メモリリーク対策
item.index = -1 // 削除されている
*pq = old[0 : n-1]
return item
}
// ここまで優先度付きキューの定義
///////////////////////////////////
/////////////////////////////
// ここから盤面構造体の定義
// Board は盤面を表す構造体
type Board struct {
h int // h は盤面の行数
w int // w は盤面の列数
cell [][]int // cell はマス目のコスト
n int // チケットの枚数
r Route // 最短経路
}
// NewBoard はBoard(盤面)のコンストラクタ
// i h : 盤面の行数
// w : 盤面の列数
// o *Board : 初期化した盤面
func NewBoard(h int, w int) *Board {
var result *Board = new(Board)
result.h = h
result.w = w
// 2次元sliceの初期化 [高さ][幅]
result.cell = make([][]int, h)
for i := range result.cell {
result.cell[i] = make([]int, w)
}
var pos Position = Position{x: 0, y: 0}
result.r = *NewRoute(pos, 0, 0, nil)
return result
}
// IsWithinRange は渡された位置が盤面の範囲内か判定する
// i p : 盤面位置
// o bool : trueなら範囲内
func (b *Board) IsWithinRange(p Position) bool {
return 0 <= p.y && p.y < b.h && 0 <= p.x && p.x < b.w
}
// GetCost は指定位置のコストを返す
// i p : 盤面位置
// o int : マスのコスト 範囲外なら-1を返す
func (b *Board) GetCost(p Position) int {
if b.IsWithinRange(p) {
return b.cell[p.y][p.x]
}
return -1
}
// dijkstra はダイクストラ法で最短経路のコストを求める
// i s : スタート位置
// g : ゴール位置
// o error : エラー
func (b *Board) dijkstra(s Position, g Position) error {
// 移動先のマス
var open PriorityQueue = make(PriorityQueue, 0)
heap.Init(&open)
// チェック済みのマス
var closed map[int]bool = make(map[int]bool)
// 開始位置にスタート地点を設定
var start *Route = NewRoute(s, b.GetCost(s), b.n, nil)
heap.Push(&open, start)
for open.Len() > 0 {
// 未チェックの経路から先頭位置を取得(移動先マスを取得)
var st *Route = heap.Pop(&open).(*Route)
// ゴール
if st.pos.Equal(&g) {
b.r = *st
return nil
}
// 移動先がすでにチェック済みのマスなら処理スキップ
// mapはキーのデータがなければ0を返す 0はbool値でfalseを表す
if closed[st.GetKey()] {
continue
}
// ここの処理に来るということは移動先マスに移動することができるということ
// 移動先マスを移動済みとして保存
closed[st.GetKey()] = true
// 次に移動するマスを追加する
// 移動可能方向数分ループし、盤面の範囲外でなければマスのコストを加算し
// 次の移動先としてリストに追加
for _, p := range MOVABLE_DIRECTION {
var destination Position = *st.pos.Plus(&p)
if b.IsWithinRange(destination) {
var newCost = st.cost + b.GetCost(destination)
// 0チケットを使わない場合
var newRoute *Route = NewRoute(destination, newCost, st.ticket, st)
heap.Push(&open, newRoute)
if st.ticket > 0 {
// 0チケットを使用した場合
var newRoute0 *Route = NewRoute(destination, st.cost, st.ticket-1, st)
heap.Push(&open, newRoute0)
}
}
}
}
// ゴールへたどり着けなかった
// 通常ならばここに来ることはない
return errors.New("ゴールへたどり着けませんでした。")
}
// ここまで盤面構造体の定義
/////////////////////////////
// convertNumArray はスペース区切り文字列を数値配列に変換する
// i str : 処理対象文字列
// o []int : 結果数値配列 変換にできない場合は0がセットされる
// []error : 変換に失敗した場合に返す
func convertNumArray(str string) ([]int, []error) {
var items []string = strings.Split(str, " ")
var length int = len(items)
var result []int = make([]int, length)
// エラーをsliceで定義
var err []error
// 配列の個数分繰り返す iに0開始のループ回数、sに要素が入る
for i, s := range items {
// intに変換
if num, e := strconv.Atoi(s); e == nil {
// 変換成功
result[i] = num
} else {
// sliceに追加
err = append(err, errors.New(fmt.Sprintf(
"[%d]番目 : [%s] 数値への変換に失敗しました。", (i+1), s)))
result[i] = 0
}
}
// エラー値はエラーがない場合はnilを返す
if len(err) == 0 {
return result, nil
} else {
return result, err
}
}
// inputData は処理に必要なデータを入力する処理
// 0 *Board : 盤面情報
// error : 処理続行不可なエラーが発生した場合に設定される
func inputData() (*Board, error) {
// 標準入力のScanner
var sc *bufio.Scanner = bufio.NewScanner(os.Stdin)
// 1行目には盤面の行数を表す h , 盤面の列数を表す w が与えらる
var ret bool = sc.Scan()
if ret == false {
return nil, errors.New("1行目が読み込めませんでした。")
}
var numbers1, err1 = convertNumArray(sc.Text())
if err1 != nil || len(numbers1) != 2 {
return nil, errors.New("1行目は不正な内容です。")
}
if numbers1[0] < 1 || 20 < numbers1[0] {
return nil, errors.New(
fmt.Sprintf("盤面の行数[%d]が範囲外です。", numbers1[0]))
}
if numbers1[1] < 1 || 20 < numbers1[1] {
return nil, errors.New(
fmt.Sprintf("盤面の列数[%d]が範囲外です。", numbers1[1]))
}
// 盤面の返却値を作成
var board = NewBoard(numbers1[0], numbers1[1])
// 2行目からのh行に盤面情報が与えられる
// 盤面情報はスペース区切りの数字文字列になっている
for i := 0; i < board.h; i++ {
var ret bool = sc.Scan()
if ret == false {
return nil, errors.New(fmt.Sprintf(
"%d行目が読み込めませんでした。", (i + 2)))
}
var line string = sc.Text()
var numbers2, err2 = convertNumArray(line)
if err2 != nil || len(numbers2) != board.w {
return nil, errors.New(fmt.Sprintf(
"%d行目は不正な内容です。[%s]", (i + 2), line))
}
for j := 0; j < board.w; j++ {
if numbers2[j] < 0 || 100 < numbers2[j] {
return nil, errors.New(fmt.Sprintf(
"%d行目のマス情報が範囲外です。[%d]", (i + 2), numbers2[j]))
}
board.cell[i][j] = numbers2[j]
}
}
// 最後の行ではチケットの枚数 n が与えられます。
ret = sc.Scan()
if ret == false {
return nil, errors.New(fmt.Sprintf("%d行目が読み込めませんでした。", board.h+2))
}
var lineN string = sc.Text()
if n, e := strconv.Atoi(lineN); e == nil {
// 変換成功
// 範囲チェック
if n < 0 || 20 < n {
return nil, errors.New(
fmt.Sprintf("チケット枚数[%d]が範囲外です。", n))
}
board.n = n
} else {
// sliceに追加
return nil, errors.New(fmt.Sprintf(
"チケット枚数が[%s]数値への変換に失敗しました。", lineN))
}
return board, nil
}
// computeData は問題を解く
// i b : 盤面情報
// o error : 処理続行不可なエラー発生時のみ返す
func computeData(b *Board) error {
if b == nil {
return errors.New("入力データがありません。")
}
// スタート位置
var start Position = Position{x: 0, y: 0}
//ゴール位置
var goal Position = Position{x: b.w - 1, y: b.h - 1}
b.dijkstra(start, goal)
return nil
}
// outputData は処理結果を出力する
// i b : 盤面情報
// o error : 処理続行不可なエラー発生時のみ返す
func outputData(b *Board) error {
if b == nil {
return errors.New("入力データがありません。")
}
// 最小のコストを出力する
fmt.Println(b.r.cost)
return nil
}
// outputRoute はたどった道筋を出力する
// i b : 盤面情報
func outputRoute(b *Board) {
// 通過経路を出力する
var path = make([][]rune, b.h)
for i := range path {
path[i] = make([]rune, b.w)
}
for y := range path {
for x := range path[y] {
path[y][x] = ' '
}
}
var r *Route = &b.r
var prev int = r.ticket
var footprint rune
for r != nil {
if r.ref != nil && prev != r.ref.ticket {
footprint = 'T' // チケット使用
prev = r.ref.ticket
} else {
footprint = '*'
}
path[r.pos.y][r.pos.x] = footprint
r = r.ref
}
for y := 0; y < b.h; y++ {
for x := 0; x < b.w; x++ {
fmt.Print(string(path[y][x]))
fmt.Print(b.cell[y][x])
}
fmt.Println("")
}
}
// main はエントリーポイント
func main() {
// データ入力
var board, err1 = inputData()
if err1 != nil {
fmt.Fprintln(os.Stderr, err1)
return
}
// 処理実行
var err2 = computeData(board)
if err2 != nil {
fmt.Fprintln(os.Stderr, err2)
return
}
// 結果出力
var err3 = outputData(board)
if err3 != nil {
fmt.Fprintln(os.Stderr, err3)
return
}
// たどった道筋を出力する
// paiza問題では不要なためコメントアウトしている
//outputRoute(board)
return
}
ビルドする
go buildコマンドで実行ファイルを作成します。
$ go build grid_dijkstra_d4.go
“grid_dijkstra_d4"という実行ファイルが作成されます。
$ $ ls -l
合計 1996
-rwxrwxr-x 1 izumi izumi 2025631 7月 26 15:17 grid_dijkstra_d4
-rw-rw-r-- 1 izumi izumi 14239 7月 26 15:17 grid_dijkstra_d4.go
実行する
実行して問題の入力例2を入力してみます。
$ ./grid_dijkstra_d4
5 12
0 1 1 1 9 9 9 9 1 1 1 1
1 1 1 1 1 9 9 9 1 9 9 1
1 1 1 9 9 9 9 9 1 9 9 1
9 2 9 9 1 1 1 1 1 9 9 1
1 1 1 2 1 9 9 9 9 9 9 1
1
20
問題の出力例2と同じ出力が確認できます。
paizaの問題では要求されていませんが、通過した道順を出力する処理も作成しています。main関数内の"outputRoute"関数のコメントを外します。
// たどった道筋を出力する
// paiza問題では不要なためコメントアウトしている
outputRoute(board)
ビルドして実行すると道順に”*“が表示されます。“T"と表示されているのはコストを0にするチケットを使用した場所を示します。
$ go build grid_dijkstra_d4.go
$ ./grid_dijkstra_d4
5 12
0 1 1 1 9 9 9 9 1 1 1 1
1 1 1 1 1 9 9 9 1 9 9 1
1 1 1 9 9 9 9 9 1 9 9 1
9 2 9 9 1 1 1 1 1 9 9 1
1 1 1 2 1 9 9 9 9 9 9 1
1
20
*0*1*1 1 9 9 9 9*1*1*1*1
1 1*1*1*1 9 9 9*1 9 9*1
1 1 1 9T9 9 9 9*1 9 9*1
9 2 9 9*1*1*1*1*1 9 9*1
1 1 1 2 1 9 9 9 9 9 9*1