「今週のお題:幅優先の二分木を深さ優先探索」問題解答 ( CodeIQ )

はじめに

CodeIQという所で週次で出題される「今週のお題」シリーズに解答しましたので、ネタバレです。

codeiq.jp

問題

今回は次のような問題でした。

  • 標準入力から空白区切りで入力される自然数m,n ( $n \le m \le 3000$ ) が与えられる
  • ノードが左から詰まっている2分木の中で、左を先にする幅優先探索順に1~mの番号を振る
  • その木の中で、左を先にする深さ優先探索順でn番目となるノードに振られた数を出力する

具体例としては、問題文にあった図をご覧ください。

https://codeiq.jp/sites/default/files/answer_ready/3197/q74.png

例えば m=10 の場合、深さ優先探索順で7番目となるのは10番のノードなので、m,n=10,7であれば10を出力する、ということになります

解説

今回、次のRubyのコードを提出しました。

p ->m,n{
  a=1
  while n>1
    b=m.bit_length
    a*=2
    l= m>>b-2<3 ? m-2**(b-2) : 2**(b-1)-1
    if n<=l+1
      n-=1
      m=l
    else
      a+=1
      n-=l+1
      m-=l+1
    end
  end
  a
}[*gets.split.map(&:to_i)]

まず先に、幅優先探索順に割り振った番号の状況を確認します。次の図にある通り、各分岐で左を辿る毎に×2、右を辿る毎に×2+1されていくのが分かります。

f:id:ange1:20170326140709p:plain

ということは、深さ優先探索で辿っていく時に、都度左右どちらを進むのか、それに応じて×2か×2+1していけば十分ということです。

では、どうすれば左右どちらを進むかが分かるのか? それは、下に木を辿っていった時の、根につながる左右の部分木の要素数を見て、前半・後半どちらに入っているかを判断することで分かります。

m=10 で調べ始める時の状況は次のような感じです。

f:id:ange1:20170326142439p:plain

そして、一旦左右どちらになるかが分かれば、その直下の部分木の中での順番が分かりますから、順次同じようにして左右を調べていくことができます。

例えば、(m,n)=(10,7)であれば、

  • 全体の7番目
  • →左の部分木の6番目
  • → 右の部分木の2番目
  • → 左の部分木の1番目

と辿ることができます

f:id:ange1:20170326144617p:plain

そのため、1から開始して、×2、×2+1、×2を繰り返していくことで10と答えが計算できます。なお、部分木の1番目になればそこで位置が確定しますから、木を辿っていくループ処理は終了です。

終わりに

幅優先、深さ優先どちらも重要なアルゴリズムですから、このような問題で両方の性質を実感しておくのも良いのではないでしょうか。