paizaの練習問題を解く隣接行列 Go編

こんにちは、ナナオです。

前回に引き続き競プロを実施していきたいと思います。

今回の問題は以下です。

隣接行列 | レベルアップ問題集 | プログラミング学習サイト【paizaラーニング】

実装

隣接行列というものがなんなのか、いまいち理解できなかったのでAIと壁打ちしました。

結果として得られた回答を要約すると以下の通りです。

「隣接行列」はただのチェック表

「頂点iと頂点jがつながっているか？」を、表の i行目とj列目が交差する場所に書き込みます。

つながっている！ → 1 を書く
つながっていない… → 0 を書く

5つの頂点がある図（1枚目の五角形のような図）で表を作ってみましょう。

つながっているペア（辺）の一覧：

1と2
1と3
2と4
3と5
4と5

これをもとに、5×5の表を埋めるとこうなります。

…ということで、なんとなくイメージがつかめてきました。

実装してみます。

package main
import "fmt"
func main(){
    var n, m int
    fmt.Scan(&n, &m)
    
    g := make([][]int, n)
    for i := 0; i < n; i++ {
        g[i] = make([]int, n)
    }
    for i := 0; i < m; i++ {
        var a, b int
        fmt.Scan(&a, &b)
        g[a - 1][b - 1] = 1
        g[b - 1][a - 1] = 1
    }
    
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            fmt.Printf("%d", g[i][j])
        }
        fmt.Println()
    }
}

これで実装できました。

一瞬戸惑いましたが、理解すればとても楽に実装できたので良かったです。

ではこれで👍

実装#

実装