【全解答付き】提示年収第1位と噂のGoを、ゲームでゼロから学んでみた！【電脳少女プログラミング2088 ─壊レタ君を再構築─】

# はじめに
　2024年12月10日、paiza株式会社が[「プログラミング言語に関する調査（2024年版）」の結果を発表](https://www.paiza.co.jp/news/20241210/241205_survey_programming_2024/)しました。その中の1つに「提示年収が高い言語ランキング」が掲載されており、第1位はGo（710.9万円）でした。しかも、2年連続で1位だそうです。
　今回は、そんな高い年収が期待できるGoを、プログラミングゲームでゼロから学んでいこうと思います。

# 概要

### ゲームタイトル
　今回学習に使用するゲームは、「電脳少女プログラミング2088 ─壊レタ君を再構築─」です。
 
https://paiza.jp/entry/denno2088_qiita

　概要としては、機械兵器化されて心を失った少女レイミを、プログラミングの力で救うという内容になっています。
　ゲーム内には、様々な難易度（S, A, B, C, Dランク）の問題が用意されているので、それらを解きながらGoの構文などについて学んでいこうという趣旨です。
　また、提出したコードに対して、レイミがコードレビューをしてくれるので、自分のコードの改善点などがわかってとても便利です。

### 筆者の経験
- 実務経験：C言語, C#, VBA
- 趣味：C++, Python


### 記事の形式
　上記の通り、Goの経験はゼロです。ですので、初歩的なものも含めて、問題ごとに私自身が学んだことをすべて書いていくので、私がゼロから学んでいく過程を見ていただけたらと思います。解説というよりは、「こういう感じなんだ～」という風に思ったことを箇条書きにしていきます。

　解答コードは、事前にC++でクリアしたコードを、そのままGoで書き直したものです。

　また、Goの特徴を他言語と比較して書くことがありますが、本ゲームの問題形式は競プロや[paizaスキルチェック](https://paiza.jp/challenges)と同じであるため、基本的には私がそれらをやるときに使っているC++やPythonの視点になることが多いと思います。

<!--
　最終的に得たものは記事の最後にまとめてありますので、そちらを見ていただければこのゲームで何を習得できるのかがわかります。
-->

### Goのバージョン
　paizaの実行環境でのバージョンは、`go version go1.19 linux/arm64`です。

# 本編
　それでは、Goの学習を始めていきましょう。

## ゲームの前に
　Goってどういうくくりの言語なのかなと、ちょっと気になったので調べました。
- オブジェクト指向の言語
  - オブジェクト指向じゃないと言っている人もいて正直わからん
- コンパイラ型言語
- 主にWebアプリケーションの開発に使われる

　へぇ～って感じのことですね。

## テンプレート
　paizaスキルチェックやpaiza提供のプログラミングゲームでは、解答に使う言語を選択するとその言語のテンプレートコードを出してくれます。まずはそれを見てみましょう。

```go
package main
import "fmt"
func main(){
    // 自分の得意な言語で
    // Let's チャレンジ！！
    fmt.Println("XXXXXX")
}
```
標準出力をするだけのシンプルなコードのようですね。
- `package main`
  - パッケージ宣言と言って、**コードの最初に書く**もの
  - 自前のパッケージ作るときは`main`の部分を変えそう
- `import "fmt"`
  - パッケージをインポートするときの書き方
  - 標準出力をするには`fmt`パッケージが必要みたい
  - Pythonっぽい
- `func main(){}`
  - main関数の宣言が必要
  - 実行の時は、**`package main`の中のmain関数が最初に呼ばれる**のかな
  - 関数宣言時は`func 関数名`って書く必要がありそう
  - `{}`でブロックを表現する
    - スコープもブロックの範囲
  - C++っぽい
- `fmt.Println("XXXXXX")`
  - 引数のものを標準出力した後に改行してくれる
  - 行終わりに`;`はいらない -> **改行で文終了**
- コメントアウトは頭に`//`
- main関数に返り値はない

　これで、Goのソースコードを書くときに、まず何を書けばいいのかがわかりました。

## 標準入力
　標準入力は、問題を解くうえで必ず行うものですが、Goでは主に以下の方法を使います。
 - `fmt.Scan()`で、区切りがある入力を直接読み込む
   - **簡単に書ける**が、遅い
 - `bufio.NewScanner()`でスキャナを生成し、1行ずつ読み込んで加工する
   - バッファリングを用いているため**速い**が、文字列を加工して各変数へ代入するのが面倒

　試しに、それぞれの方法で標準入力を読み込んでみます。

### `fmt`

**入力**
```
1 10 hello
```

**コード**
```go
package main

import "fmt"

func main() {
    // n1, n2 を宣言（整数型）
    // s を宣言（文字列型）

    // 標準入力を読込
    fmt.Scan(&n1, &n2, &s)
    
    // ...（続く処理）
}
```
- 変数の**アドレスを渡す**ことで、入力データが順番に格納される
  - `&変数名`とすると、その変数のアドレスを取得できる
- 区切り文字は、**空白**と**改行**
- 入力するデータが少なく、データ数や型が事前にわかっている場合はこちらが使える
- **違う型のデータが混在していても、手間なく取得できる**

### `bufio`
**入力**
```
10
1 2 3 4 5 6 7 8 9 10
```
（1行目：データ数、2行目：データ）

**コード**
```go
package main

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

func main() {
    // N を宣言（整数型）
    
    // データ数を読込
    fmt.Scan(&N)

    // スキャナを生成
	sc := bufio.NewScanner(os.Stdin)
    // 1行分読み込む
	sc.Scan()
    // 空白で分けて配列として格納（この時点では文字列型）
	input := strings.Split(sc.Text(), " ")

	// A を宣言（整数型配列（スライス）、サイズ N）

    // N 回繰り返し
	for i := 0; i < N; i++ {
        // 1つずつ、整数に変換して格納
		A[i], _ = strconv.Atoi(input[i])
	}
    
    // ...（続く処理）
}
```
- 標準入力の流れ
  - `bufio.NewScanner(os.Stdin)`で、標準入力用の**スキャナを生成**できる
    - `bufio`と`os`のインポートが必要
  - `Scan()`メソッドで、**1行分**の入力を読み込める（改行で取得が中断される）
  - `Text()`メソッドで、読み込んだ文字列を取得できる
  - `string.Split()`メソッドで、**空白区切りで文字列を分ける**
    - `string`のインポートが必要
  - `strconv.Atoi()`で、文字列から**整数に変換**する
    - `strconv`のインポートが必要
- **データ数が変わる場合**は、こちらを使う必要がある
- **データサイズが大きい場合**は、こちらを使った方が圧倒的に速い

※上の例では、やむを得ず変数宣言やfor文が登場していますが、これらは以降の問題を解く際に詳しく書きます。

　問題を解く上ではこれで十分です。実際には、汎用性を持たせたり、例外処理を加えたりするのでしょうが、詳しく知りたい方はこちらの記事を参考にすると良いと思います。

https://qiita.com/zurazurataicho/items/e66645bac16d9a482369

　また以降は、コードが長くなる場合、必要のない限りは標準入力部分を省略して書きます。

　次の章からは、いよいよゲームの問題を実際に解いていきます。

## Dランク

### カジノ
　1ドル、5ドル、10ドルのチップのそれぞれの枚数が与えられるので、合計で何ドルかを求めます。

**必要なこと**
- 枚数を格納する変数の宣言
- 合計を求めるための加算と乗算

　今回は、配列に枚数を格納します。
```go
package main

import "fmt"

func main() {
    // サイズ 3 の配列を宣言
    var chip [3]int
    // 入力
    fmt.Scan(&chip[0], &chip[1], &chip[2])
    // 合計を計算して出力
    fmt.Println(chip[0] + 5*chip[1] + 10*chip[2])
}
```

- 変数は、`var 変数名 型`で宣言できる
  - 配列の場合は、型の前に`[数字]`をつける
- 配列内の要素は`変数名[番号]`で取得できる
- 四則演算：`+ - * /`
- `fmt.Println()`に渡すのが整数型でもちゃんと出力してくれる

　変数宣言以外は、他の言語と変わらないですね。

### 郊外のスラム街
　$n$円のジャンク品を値切ります。
- ファーストプラン：半分の金額
- セカンドプラン：$上の金額+100$円

　セカンドプランの金額を求めます。

**必要なこと**
- 金額を求めるための除算

```go
package main

import "fmt"

func main() {
    var n int
    fmt.Scan(&n)
    // 金額を計算して出力
    fmt.Println(n/2 + 100)
}
```
- **`int`型同士の除算の結果は`int`型になる**
  - 小数点以下切り捨て
- どちらか1つでも少数が含まれていると、結果は浮動小数点数になる
  - 具体的には`float64`（64ビットの浮動小数点数）

　こちらも特に変わったところは無いですね。

### ネオン街の裏路地
　$n$個の扉に数字が書かれているので、一番大きい数字を求めます。

**必要なこと**
- 要素数が固定じゃない場合の、データを格納する変数の宣言
- 最大値を求める処理

```go
package main

// 複数のインポート
import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func main() {
	var n int
	fmt.Scan(&n)

    // ドアの数字を格納するスライスを宣言
	doorNums := make([]int, n)
    
    // ...（ドアの数字を読込）

    // 答え用（-1で初期化）
	var ans int = -1
    // 格納されている要素分繰り返す
	for _, num := range doorNums {
        // 大きかったら入れ替える
		if num > ans {
            ans = num
        }
	}

	fmt.Println(ans)
}
```
- `import`は、複数ある場合は`()`でまとめられる
- 変数宣言にはいくつか種類がある
  - `var ans int = -1`
    - 宣言に続けて`= 値`と書くことで**初期化ができる**
    - 初期化する場合は型を省略でき、省略すると初期化した値から型が推測される
  - `ans := -1`
    - 初期化した値から型が推測される
    - 関数内でしか使えない
- **実行前に要素数がわからない場合は、スライスとして変数を宣言**する
  - `make([]型, 要素数)`で、スライスを作成できる
  - 配列は要素数が**固定**、スライスは要素数が**可変**（追加・削除ができる）
  - 配列にしようとして`var doorNums [n]int`とするとエラーになる
  - C言語の静的配列と動的配列と同じイメージ
- 制御文（`if`、`for`など）で、条件を書く際に`()`がいらない
  - `{}`は必須で、**省略できない**
- `for`文にはいくつか種類がある
  - `for i := 0; i < n; i++`
    - `初期; 条件; 更新`の形（上は、$i=0, \dots, n-1$で繰り返す）
    - 多くの言語でよく見るタイプ
  - **`for index, element := range array`**
    - `array`の要素の数だけ繰り返す
    - `index`に要素番号、`element`に値が入る
      - Goでは複数の返り値を複数の変数に代入することができ、**多重代入**と呼ばれる
    - Pythonの`for index, element in enumerate(array)`と同じイメージ
    - 解答コードでは、`_, num`で値のみを取得している（`_`はダミー変数）
- `if`文は、`if`の後に書いた条件が真ならば`{}`内が実行される
- 比較演算子：等しい`==`、等しくない`!=`、より小さい`<`、より大きい`>`、以下`<=`、以上`>=`

　条件文が`()`で囲われていないと、ちょっとそわそわしてしまう。

:::note info
バージョン1.21以降であれば、一番大きい値を返す`max()`や、スライス内の最大値を返す`slices.Max()`が使えるので、さらに簡潔に書けます。
:::

## Cランク

### 自然の残る公園
　公園に、$N$個のビーコン反応があり、番号が付けられています。現在の座標$(Y,X)$から最も近いビーコンの番号を求めます。

**必要なこと**
- 距離計算
- 最大距離と番号の保持

```go
package main

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

func main() {
	// 無限大を定義
	inf := math.MaxInt

	var N, Y, X int
	fmt.Scan(&N, &Y, &X)

	sc := bufio.NewScanner(os.Stdin)
	// 番号と距離を記録
	index, minDist := -1, inf
	for i := 0; i < N; i++ {
        // y, x を読込

		dist := (x-X)*(x-X) + (y-Y)*(y-Y)
		if dist < minDist {
			// 距離が短いもので更新
			index, minDist = i, dist
		}
	}

	// 番号を出力
	fmt.Println(index + 1)
}
```
- `math.MaxInt`で、`int`型の最大値が取得できる
  - 最小値、`float64`型の正・負の無限大もある
  - `math`のインポートが必要
- 値を複数代入するときに、**多重代入**が便利

### 廃マンションの一室
　廃マンションの扉のセキュリティには、以下の特殊な3進数を採用したコンピュータが使われています。
```math
0_{(3)} = 0_{(10)},\ 1_{(3)} = 1_{(10)},\ 2_{(3)} = -1_{(10)}
```
　10進表記の数字$N$から、上記の変換をした3進数を求めます。

**必要なこと**
- 余りの計算
- 複数の条件分岐
- 3進数を一桁ずつ求めるための繰り返し
- 一桁ずつスライスへ格納する処理
- スライスから3進表記にして表示する処理

```go
package main

import (
	"fmt"
	"os"
)

func main() {
	var N int
	fmt.Scan(&N)

	isPos := true
	if N < 0 {
		// 元の符号を記録しておく
		isPos = false
		// 必ず正の値で変換を行う
		N = -N
	} else if N == 0 {
		// 0ならそれを出力して終了
		fmt.Println(0)
		os.Exit(0)
	}

	// 3進表記の各桁を格納するためのスライス
	ans := make([]int, 0)
	// N が 0 になるまで
	for N > 0 {
		// 余りの計算
		md := N % 3
        
		// 余りによって各桁の数字を決める
		ans = append(ans, md)
		// 特殊な3進数の対応
		if md == 2 {
			N += 3
		}

		N /= 3
	}

	// 逆順にして出力
	if isPos {
		// 正の場合
		for i := len(ans) - 1; i >= 0; i-- {
			fmt.Print(ans[i])
		}
	} else {
		// 負の場合
		minusTrans := [...]int{0, 2, 1}
		for i := len(ans) - 1; i >= 0; i-- {
			fmt.Print(minusTrans[ans[i]])
		}
	}
	fmt.Println()
}
```

- `bool`型の要素は`true, false`（小文字）
- `if-else`文もほかの言語と特に変わらない
- プログラムを終了するときは`os.Exit()`を使う
  - 引数：正常終了ならば`0`、異常終了ならば`1`
- Goに **`while`文は無い**が、`for`文で同じように書くことで`while`文と同じ処理ができる
- `append(slice, value)`で`slice`の末尾に`value`を追加する
  - 正確には、**追加された状態のスライスが返される（直接追加されるわけではない）** ので、変数に代入する必要がある
  - Goは、こういった操作は組み込み関数や静的メソッドでやって、インスタンスメソッドはあまり使わないのかなという印象
- `%`で余りの計算ができる
- `+=`、`/=`といった、演算して再代入する演算子もある
- `[]型{要素1, 要素2, ...}`とすることで、**配列・スライス初期化**ができる
  - 先頭の部分を`[...]`にすると配列、`[]`にするとスライスとして宣言できる
  - 初期化をしている場合は、`[...]`で配列サイズを適当に決めてくれる
- インクリメント・デクリメントは一応ある
  - 後置のみで、前置はできない
  - 単体でのみ使用でき、式の中では使用できない

### （ネオン街のクラブ）
　※イベント終了後に記載します

## Bランク

### ギャングのアジト
　ギャングが縄張りを示すためにピクセルアートを壁に描き残しています。あるギャングのピクセルアートには特徴があり、黒と白で塗られた左右対称のピクセルアートだそうです。
　$N \times N$のピクセルアートが左右対称かどうかを求めます。

**必要なこと**
- 2次元スライス
- 2重ループ
- ループを中断する処理

```go
package main

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

func main() {
	var N int
	fmt.Scan(&N)

	// ピクセルアートを格納する整数型2次元配列
	pixelArt := make([][]int, N)

    // ...（PixelArt を読込）
    
	ans := true
	// 縦に半分にした範囲を探索
	for i := 0; i < N; i++ {
		for j := 0; j < N/2; j++ {
			// 左右対称でないものがあったら終了
			if pixelArt[i][j] != pixelArt[i][N-j-1] {
				ans = false
				break
			}
		}
		// すでに false なら終了
		if !ans {
			break
		}
	}

	if ans {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}
```
- 配列・スライスの次元を増やすときは、`[]`の数を増やす
  - スライスの場合、**宣言直後の1次元目以外の要素は`nil`（Nullポインタ）** なので、そのままでは参照できないことに注意する
- ループを中断するときは`break`

### 一番通りの繁華街
　$N \times N$のグリッド上に、ギャングのアジトの建物が$N$個あります。ギャングたちの間では、自分たちの建物を線でつないだ時に、正方形になる地域を自分たちの縄張りとすると取り決められています。
　与えられたグリッド内に、縄張りがいくつあるのかを求めます。

**必要なこと**
- 文字列の処理
- n重ループ
- ループ内でスキップする処理
- 複数条件の組み合わせ

```go
package main

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

// 大きい方を返す関数
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	var N int
	fmt.Scan(&N)

	// グリッドを格納する文字型2次元配列
    // アジトの建物:'.', 空地:'#' で表現されている
	grid := make([][]rune, N)
    // グリッドを読込
	sc := bufio.NewScanner(os.Stdin)
	for i := 0; i < N; i++ {
		sc.Scan()
		// string を rune のスライスとして格納
		grid[i] = []rune(sc.Text())
	}

	ans := 0
	// 終端以外を全探索
	for i := 0; i < N-1; i++ {
		for j := 0; j < N-1; j++ {
			// 左上がアジトではない場合はスキップ
			if grid[i][j] == '#' {
				continue
			}
            
			// (i, j) を左上とした正方形を全探索
            limit := N - max(i, j)
            for k := 1; k < limit; k++ {
				// 4つの頂点がすべてアジトなら +1
				if grid[i][j+k] == '.' && grid[i+k][j] == '.' && grid[i+k][j+k] == '.' {
					ans++
				}
			}
		}
	}

	fmt.Println(ans)
}
```
- 関数定義は、`func 関数名(引数1, 引数2, ...) 戻り値1, 戻り値2, ... {}`で行える
  - 引数、戻り値は0個以上
  - （戻り値にも変数名をつけることができる）
- Goの**文字型は`rune`**
  - `int32`型のエイリアス
- `[]rune(文字列)`とすると、**文字列を`rune`型のスライスに変換**して返してくれる
  - 今回は`string`型のままでも問題ない
  - **マルチバイト文字（日本語、絵文字など）があると、`string`型の添え字の参照ではうまく参照できない**
  - `rune`型のスライスを用いた方が**汎用的**
- ループ内でスキップするときは`continue`
- 論理演算子：論理積`&&`、論理和`||`、否定`!`

　`rune`はルーン文字が語源らしい。

:::note info
バージョン1.21以降であれば、`max()`が標準で使えます。
:::

## Aランク

### 新都心のハイウェイ

　車両$A$と車両$B$が、$H \times W$マスからなるハイウェイ上にいます。$A$は、壁がないところを移動でき、壁にさえぎられていない直線上のマスを見渡すことができます。また、$B$は初期位置から移動しません。
　$A$が$B$を見つけられるマスへ移動するために必要な移動回数の最小値を求めます。

**必要なこと**
- [幅優先探索（BFS）](https://qiita.com/drken/items/996d80bcae64649a6580)
  - キューを用いた管理
- キューに入れる情報をまとめた構造体

```go
package main

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

// 上下左右
var dy = [4]int{-1, 0, 1, 0}
var dx = [4]int{0, 1, 0, -1}

// キューに入れる情報
type state struct {
	// 座標:(i,j), 移動回数:dist
	i, j, dist int
}

func main() {
	var H, W int
	fmt.Scan(&H, &W)

	// グリッド用スライス
	// 道:'.', 壁:'#' で表現されている
	grid := make([][]rune, H)
	// A, B の初期位置の座標
	var Ai, Aj, Bi, Bj int
	sc := bufio.NewScanner(os.Stdin)
    // グリッドを読込
	for i := 0; i < H; i++ {
		sc.Scan()
		grid[i] = []rune(sc.Text())
		for j := 0; j < W; j++ {
			// 座標を記録
			if grid[i][j] == 'A' {
				Ai, Aj = i, j
			} else if grid[i][j] == 'B' {
				Bi, Bj = i, j
			}
		}
	}

	// (i,j) がグリッド内の道かどうかを判定する関数
    isLoad := func(i, j int) bool {
		return (0 <= i && i < H && 0 <= j && j < W && grid[i][j] != '#')
	}

	// B が見えるマスをすべて B にする
	for d := 0; d < 4; d++ {
		ni, nj := Bi+dy[d], Bj+dx[d]
		for isLoad(ni, nj) {
			grid[ni][nj] = 'B'
			ni, nj = ni+dy[d], nj+dx[d]
		}
	}

	// 初期位置ですでに見つけられる場合はそれを出力して終了
	if grid[Ai][Aj] == 'B' {
		fmt.Println(0)
		os.Exit(0)
	}

	// キューとして使うスライス
	bfsQueue := make([]state, 0)
	bfsQueue = append(bfsQueue, state{Ai, Aj, 0})
	grid[Ai][Aj] = '#'
	// BFS
	for len(bfsQueue) > 0 {
		// キューの先頭を取得
		i, j, dist := bfsQueue[0].i, bfsQueue[0].j, bfsQueue[0].dist
		// キューからポップ
		bfsQueue = bfsQueue[1:]

		for d := 0; d < 4; d++ {
			ni, nj := i+dy[d], j+dx[d]
			if isLoad(ni, nj) {
				// B を見つけたら移動回数を出力して終了
				if grid[ni][nj] == 'B' {
					fmt.Println(dist + 1)
					os.Exit(0)
				}
				// キューにプッシュ
				bfsQueue = append(bfsQueue, state{ni, nj, dist + 1})
				// 探索済みの印として # を置く
				grid[ni][nj] = '#'
			}
		}
	}

	// 見つけられない場合は -1 を出力
	fmt.Println(-1)
}
```
- 他の言語の`class`や、C++の構造体なんかと同じように構造体を使いたい場合は以下のように書けば良い
  ```go
  type 構造体名 struct {
      フィールド1
      フィールド2
      ...
  }
  ```
[⇒ ちょっと細かい話](#構造体structについて)
- グローバル領域でも同じように変数を宣言できるが、いくつか注意が必要
  - `変数名 := 値`の形の宣言は使えない
  - 変数を、パッケージ内でのみ使うようにするときは、変数名の頭文字を小文字にする
  - 頭文字を大文字にすると、他のパッケージからも参照できるようになる（関数も同様）
  - よく見ると、コード内で呼び出しているパッケージのメソッドは、すべて頭文字が大文字
- 関数内で、**無名関数**（ラムダ式のようなもの）を定義、変数に代入することができる
  - 普通の関数宣言で書いて、そのまま変数に入れられるので簡単
  - 定義した場所のスコープ内の変数を参照できる（参照キャプチャ）
- **スライスの参照の仕方：`slice[left:right:cap]`** 
  - `left` ：この添え字以降の範囲を参照する（省略すると先頭から）
  - `right`：この添え字より前の範囲を参照する（省略すると末尾まで）
  - `cap`  ：参照する範囲の最大値（省略すると制限なし）
  - **$\rm [left, right)$の範囲で、最大$\rm cap$個分取得する**
- **キュー・スタックを使うときは**、専用のパッケージがないため、**スライスを用いて管理する**
  - プッシュ：`append`で末尾に追加
  - 先頭の取得：添え字で`[0]`を指定すればよい
  - ポップ：添え字で`[1:]`を指定して、先頭を除いたスライスを取得する
  - （ちゃんとキューとしての操作しかできないように、構造体とかで定義したほうが安全なんじゃないかと思ってきた）

　使い方次第で工夫できそうなものがたくさんある。

## Sランク

### 思い出の屋上
　$H \times W$のグリッド上に$M$個の縄張りがあります。$i$番目の縄張りの範囲は、縄張りのサイズ$S_i$に対して、座標$(R_i,C_i)$からマンハッタン距離が$S_i$以下のすべてのマスです。
　すでにある縄張りに重ならないよう新たに縄張りを作るとき、縄張りのサイズ$S$としてあり得る最大値を求めます。

　この問題については、自分の解法を解説した記事を出しているので、気になる方は是非読んでみてください。

https://qiita.com/RotterYkrn/items/b516264279bd7793c57f

**必要なこと**
- これまでのすべての知識
- 解法を導き出す力

```go
package main

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

// 上下左右
var dy = [4]int{-1, 0, 1, 0}
var dx = [4]int{0, 1, 0, -1}

// キューに保存する情報
type state struct {
	// 座標:(r, c), 探索距離:d
	r, c, d int
}

// 大きい方を代入する関数
func chmax(a *int, b int) {
	if *a < b {
		*a = b
	}
}

func main() {
	var H, W, M int
	fmt.Scan(&H, &W, &M)

	// グリッド用スライス
	grid := make([][]int, H)
	for i := 0; i < H; i++ {
		grid[i] = make([]int, W)
	}

	// 縄張り探索用のキュー
	territoryQue := make([]state, 0)
	// 縄張りの情報を読込
	sc := bufio.NewScanner(os.Stdin)
	for i := 0; i < M; i++ {
		sc.Scan()
		input := strings.Split(sc.Text(), " ")
		R, _ := strconv.Atoi(input[0])
		R--
		C, _ := strconv.Atoi(input[1])
		C--
		S, _ := strconv.Atoi(input[2])

		// キューに保存
		territoryQue = append(territoryQue, state{R, C, S})
		grid[R][C] = 1
	}

	// (r,c) がグリッド内かどうかを判定する関数
	isInGrid := func(r, c int) bool {
		return (0 <= r && r < H && 0 <= c && c < W)
	}

	solutionQue := make([]state, 0)
	// BFSで縄張りを記録
	for len(territoryQue) > 0 {
		r, c, d := territoryQue[0].r, territoryQue[0].c, territoryQue[0].d
		territoryQue = territoryQue[1:]

		for i := 0; i < 4; i++ {
			nr, nc := r+dy[i], c+dx[i]
			if isInGrid(nr, nc) && grid[nr][nc] != 1 {
				// dを減らしていき、0になったら終了
				if d > 0 {
					territoryQue = append(territoryQue, state{nr, nc, d - 1})
					grid[nr][nc] = 1
				} else if grid[nr][nc] != 2 {
					// 外縁の座標を保存
					solutionQue = append(solutionQue, state{nr, nc, 0})
					grid[nr][nc] = 2
				}
			}
		}
	}

	ans := -1
	// BFSで空きマスを探索
	for len(solutionQue) > 0 {
		r, c, d := solutionQue[0].r, solutionQue[0].c, solutionQue[0].d
		solutionQue = solutionQue[1:]

		// 外縁だが、他の縄張り内であるためスルー
		if grid[r][c] == 1 {
			continue
		}

		// 探索距離が長いものを保存
		chmax(&ans, d)

		for i := 0; i < 4; i++ {
			nr, nc := r+dy[i], c+dx[i]
			if isInGrid(nr, nc) && grid[nr][nc] == 0 {
				solutionQue = append(solutionQue, state{nr, nc, d + 1})
				grid[nr][nc] = 2
			}
		}
	}

	fmt.Println(ans)
}
```

- `*`を用いることで、ポインタを扱える
  - 関数内での変更を呼び出し元でも反映させたいときは、ポインタ渡しを使う（参照渡しは無い）

　2次元スライスの初期化が少し面倒だった。

**おまけ**

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3996320/ac7b4e7a-84e0-716e-d9b8-37c42915e5d7.png)

　コードをしっかりと書けば、とてつもなく評価してくれる[^reimi]。
[^reimi]: ちなみに、親密度によってレビューのセリフが変わるらしく、これは最上級の評価。

# さいごに
　今回は、Goのコードについてゲームをしながら学んでみました。もちろん、業務で使うためには、モジュールの設計やフレームワークなどを学ばなければなりません。しかし、基本的な機能や文法についての知識をあらかじめ学んでおくと、追加で学ぶ際に立ち止まってしまうことが少なくなります。**基礎はとても大事です。** 普段なら面倒な基礎学習も、ゲームでやれば少しはやる気が出るでしょう。これからも楽しみながら、自分のスキルを磨いていきましょう！

　（学んだことのまとめは、やる気があればそのうち書きます。）

# 付録

## 構造体`struct`について

　まず、構造体は型の一種であり、**下記の部分が構造体の型としての表現部分**です。
```go
struct {
    フィールド1
    フィールド2
    ...
}
```
ですので、構造体型の変数を宣言する際、本来は、
```go
// 初期化なし
var 変数名 struct {
    フィールド1
    フィールド2
    ...
}

// 初期化あり
var 変数名 = struct {
    フィールド1
    フィールド2
    ...
}{値1, 値2, ...}
```
と、構造体の中身を毎回書かなければなりません。

　そこで、`type`を使って以下のように構造体を定義します。
```Go
type 構造体名 struct {
    フィールド1
    フィールド2
    ...
}
```
　`type`はどのような役割かと言いますと、構造体の不便を解消するために作られたもの・・・・・・というわけではなく、簡単に言えば**型の名前を新しく定義**できるものです。ですので、例えば`type char rune`と書くと、`rune`型に新しい名前`char`を定義して、`char`を使って文字型を表せるようになります。要するに、C言語の`typedef`や、C++の`using`みたいなものです。

　`type`を使って上記のように構造体名を定義することにより、以下のように簡潔に書けるようになるというわけです。
```go
// 初期化なし
var 変数名 構造体名

// 初期化あり
var 変数名 = 構造体名{値1, 値2, ...}
```

　詳しくは、以下の記事を参考にしてください。

https://qiita.com/tenntenn/items/45c568d43e950292bc31

## 並行処理を使ってみよう！
　Goでは、簡単に並行処理を実現することができるらしいので、もちろんやってみます。やってみたいですよね？ というわけでやっていきます。

### 必要な知識
　Goの並行処理に関する知識を、超ざっくりとまとめます。

- ゴルーチン（goroutine）
  - **並行処理をするように実行した関数**
  - 関数を呼び出すときに、頭に`go`をつけると並行処理で実行するようになる
  - 呼び出しただけだと、呼び出し元と完全に非同期になって困るので、追加で同期処理を混ぜていく
    - ゴルーチンが完了する前にプログラムが終了してしまうなど
- `sync`パッケージ
  - **並行処理の管理**、**排他制御**などの機能が使える
- チャネル（channel）
  - ゴルーチンとの**データの送受信**ができる
  - 受信待ち、送信待ちを使うことで、同期するタイミングを決めることができる
- select
  - チャネルとセットで使われる
  - 複数のチャネルを非同期で受け取ったりできる

### 実装
　本編で扱った2つの問題について、一部だけ並行処理を用いて実装してみましょう。（実装の仕方を理解するのが目的なので、なかば強引に並行処理を組み込んでます。）

#### [一番通りの繁華街](#一番通りの繁華街) 
　縄張りの探索部分を並行処理させてみる。

**使用したもの**
- ゴルーチン
- `sync`パッケージ
  - `sync.WaitGroup`
  - `sync.Mutex`

```diff_go
package main

import (
	"bufio"
	"fmt"
	"os"
+	"sync"
)

// 大きい方を返す関数
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	var N int
	grid := make([][]rune, N)
    
    // ...（データを入力）

	ans := 0
+   wg := sync.WaitGroup{} // 並行処理管理用
+   lock := sync.Mutex{}   // 排他制御用
	// 終端以外を全探索
	for i := 0; i < N-1; i++ {
		for j := 0; j < N-1; j++ {
			// 左上がアジトではない場合はスキップ
			if grid[i][j] == '#' {
				continue
			}

+			// 実行中のゴルーチンをカウントアップ
+			wg.Add(1)
+			// ゴルーチン実行
+			go func(fi, fj int) {
+				// ゴルーチン終了時にカウントダウン
+				defer wg.Done()

				// (i, j) を左上とした正方形を全探索
				limit := N - max(fi, fj)
				for k := 1; k < limit; k++ {
					// 4つの頂点がすべてアジトなら +1
					if grid[fi][fj+k] == '.' && grid[fi+k][fj] == '.' && grid[fi+k][fj+k] == '.' {
+						// 競合が起きないように排他制御
+						lock.Lock()
						ans++
+						lock.Unlock()
					}
				}
+			}(i, j)
		}
	}
+	// すべてのゴルーチンが終了するまで待機
+	wg.Wait()

	fmt.Println(ans)
}
```
- `sync.WaitGroup`で、並行処理を管理する
  - コード内では、**動作中のゴルーチンの数を管理**している
  - `Add()`：実行中のゴルーチンの数を増やす
  - `Done()`：ゴルーチンの実行終了を伝えて、管理してる数を1減らす
  - `Wait()`：実行中ゴルーチンの数が0になるまでブロックする
- `sync.Mutex`で、**排他制御**を実現する
  - 複数同時のメモリアクセスを無くすことで、不整合を起こさないようにする
  - `Lock()`：他の場所でのメモリの読み書きを禁止する
  - `Unlock()`：読み書き禁止を解除する
- 先頭に`defer`をつけると、その処理は関数`return`時に実行される

　ちなみに、最初に排他制御を入れずに提出したら、普通に指摘されて改善案まで示してもらえました。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3996320/a37f5ff2-5bfd-8f96-a38e-ecdcc19dc1e0.png)

#### [新都心のハイウェイ](#新都心のハイウェイ)
　車両$A$と車両$B$の初期位置を、並行処理で探してみる。

**使用したもの**
- ゴルーチン
- チャネル
- select

```diff_go
package main

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

// 上下左右
var dy = [4]int{-1, 0, 1, 0}
var dx = [4]int{0, 1, 0, -1}

// キューに入れる情報
type state struct {
	// 座標:(i,j), 移動回数:dist
	i, j, dist int
}

func main() {
	var H, W int
	fmt.Scan(&H, &W)

	// グリッド用スライス
	// 道:'.', 壁:'#' で表現されている
	grid := make([][]rune, H)
	// A, B の初期位置の座標
	var Ai, Aj, Bi, Bj int
	sc := bufio.NewScanner(os.Stdin)
+   // A, B の座標を送受信するためのチャネル
+	chA, chB := make(chan state), make(chan state)
	// グリッドを読込
	for i := 0; i < H; i++ {
		sc.Scan()
		grid[i] = []rune(sc.Text())
+       // ゴルーチン実行
+		go func(fi int) {
			for j := 0; j < W; j++ {
+				// 座標を送信
				if grid[fi][j] == 'A' {
-                   Ai, Aj = i, j
+					chA <- state{fi, j, 0}
				} else if grid[fi][j] == 'B' {
-                   Bi, Bj = i, j
+					chB <- state{fi, j, 0}
				}
			}
+		}(i)
	}

+	closedA, closedB := false, false
+   // A, B の座標を受信するまでブロック
+	for !closedA || !closedB {
+       // 一度に複数の受信を待てる
+		select {
+		case s := <-chA:
+			Ai, Aj = s.i, s.j
+			closedA = true
+		case s := <-chB:
+			Bi, Bj = s.i, s.j
+			closedB = true
+		}
+	}

+   // チャネルを閉じる
+	close(chA)
+	close(chB)

    // ...（答えを求める）
}
```
- チャネルを使って、データの送受信を行える
  - `ch = make(chan 送受信する型)`で、チャネルを生成する
  - `ch <- 値`で、データを送信する
  - `<-ch`で、データを受信できる
    - `変数名 = <-ch`とすると、受信したデータを変数に代入できる
  - 送信・受信は、相手の準備ができるまでブロックされる
  - 使い終わったチャネルは、`close(ch)`で閉じる
    - クローズしたチャネルは、送信はできなくなり、受信は常にゼロ値が返される
- `select`を使って、複数のチャネルの受信を待つ
  - `<-chA`とすると、`chB`への送信はブロックされたまま
  - `select`を用いることで、`chA`と`chB`の両方で送信が可能になる

　その他、詳しいことは以下の記事を参考にしてください。

https://qiita.com/yumauma20/items/b5c8e76da8edc864b58b

## 学習のときに爆笑した瞬間

https://x.com/RotterYkrn/status/1884626183817736408?t=_qvoBNimyG82pXw3ogpvXA&s=19

　「？？？」じゃないが。