山傘のプログラミング勉強日記

プログラミングに関する日記とどうでもよい雑記からなるブログです。

ビットすごろく

yukicoderのレベル1の問題を10題ほど解いたのでレベル2の問題を解こうと思い、ビットすごろくなるものを解いてみました。

No.3 ビットすごろく - yukicoder

なんのことかよく分からなかったので、N=3の場合、有向グラフを書いて見るとなんのことか分かりました。Nのときの隣接行列をAとすると、A^(m)(1, N)が1以上であれば、1からNの経路が存在することになります。mは1<= m <=N-1の範囲に存在する整数です。したがって、隣接行列Aのべき乗を求めることで解答を得ることができました。詳しい内容は離散数学で学べます。

しかし、この方法は冗長?みたいです。解説しているサイトを見ると、幅優先探索なるアルゴリズムで解けるみたいです。