ebisukeプログラミング初心者脱出黙示録

30歳を過ぎてから始めたプログラミングと競プロの記録。Pythonで取り組んでいます。Arduinoで電子工作も

【AtCoder版!蟻本】AOJ 0503 Cup【幅優先探索】

f:id:ebisuke33:20210327124717p:plain
AtCoder版!蟻本幅優先探索で類題としてあげられているAOJ 0503 CupをPythonで解いていきます。

AOJ 0503 Cup

AOJ 0503 Cup

問題文

大きさが異なる n 個のコップと 3 つのトレイ(お盆)A,B,C があり,それらのコップは 3 つのトレイの上にそれぞれ何個かずつ一山に重ねて置かれている.ただし,どのトレイにおいても,そのトレイの中で一番小さいコップが一番下に, 2 番目に小さいコップがその上に, 3 番目に小さいコップがその上にと,小さい順に伏せて重ねてある.例えば,下図の右側は, n = 5 個のコップがトレイ A,B,C にそれぞれ 2 個,0 個,3 個重ねて置かれている状態を示している.

このように,コップの初期状態が与えられたとき,次の規則 1 〜 3 を守りながら,すべてのコップを A または C のどちらかのトレイに移動させるには何回移動を行えばよいかを求めたい.

(規則 1) 1 回に 1 つのコップだけを移動させることができる.それは,そのトレイにあるコップの中で一番上のコップ(つまり,一番大きいコップ)である.

(規則 2)大きいコップの上に小さいコップを重ねてはいけない.

(規則 3)コップ 1 個の直接移動は,トレイ A から B,B から A,B から C,C から B のみが許され, A から C への直接移動や C から A への直接移動は許されない.

n 個のコップの初期状態と整数 m が与えられたとき, m 回以内の移動で, A または C のどちらかのトレイにすべてのコップをまとめて重ねることができるかどうかを判定し,可能な場合には移動回数の最小値を,不可能な場合には -1 を出力するプログラムを作成しなさい.

解答例

from collections import deque

# n = 0, m = 0まで無限ループ
while True:
    n, m = map(int,input().split())
    # 終了条件ならループ終了
    if n == 0 and m == 0:
        break

    # トレイAの配列
    A = list(map(int,input().split()))
    # トレイBの配列
    B = list(map(int,input().split()))
    # トレイCの配列
    C = list(map(int,input().split()))
    
    # 入力の先頭要素を0に入れ替える
    A = [0] + A[1:]
    B = [0] + B[1:]
    C = [0] + C[1:]

    que = deque()
    que.append([A, B, C, 0, -1])
    # ひとつのトレイにすべてのコップをまとめた状態と同じ配列targetを作成
    target = []
    for i in range(n+1):
        target.append(i)

    # 移動回数を調べるbfs
    while que != 0:
        # dは移動回数、tは前回のどこからどこに移動したか表す値
        a,b,c,d,t = que.popleft()
        # 移動回数がmを超えればbreak
        if d > m:
            print(-1)
            break
        # トレイAかトレイCが目標のtargetと同じになれば完成
        if a == target or c == target:
            print(d)
            break
        # トレイA -> トレイBに移動
        if a[-1] > b[-1] and t != 1:
            que.append([a[:-1], b+[a[-1]], c[:], d+1, 0])
        # トレイA <- トレイBに移動
        if b[-1] > a[-1] and t != 0:
            que.append([a+[b[-1]], b[:-1], c[:], d+1, 1])
        # トレイB -> トレイCに移動
        if b[-1] > c[-1] and t != 3:
            que.append([a[:], b[:-1], c+[b[-1]], d+1, 2])
        # トレイB <- トレイCに移動
        if c[-1] > b[-1] and t != 2:
            que.append([a[:], b+[c[-1]], c[:-1], d+1, 3])

解説

i番目の大きさがiであるN個のコップとA,B,Cの3つのトレイがあります。
コップは自身より小さいものに対しては重ねることができます。
初期条件からm回コップを動かして、AまたはCのトレイにすべてまとめることができるかどうか答える問題です。

ひとつのトレイにすべてのコップをまとめた状態と同じ配列targetを作成して、この配列targetを作ることができるかBFSしていきます。

キューに初期条件として([A, B, C, 0, -1])を入れます。
トレイA,B,Cの配列と、移動回数d = 0、そして前回の移動元を表すtは-1としました。

BFSでは移動回数dがmを超えるか、targetと同じ配列ができればbreakします。
breakするまではトレイA,B,Cにおいてコップの移動を試し続けていきます。
移動元と移動先のコップの大きさを比較し、前回の移動前と同じ配列にならないならキューに加えます。
移動先によって配列A,B,Cの要素を変更し、移動回数dに1を加え、移動元データtを更新します。
この操作を繰り返してbreakするまで幅優先探索を行っていき、求まった答えを解答します。


このような問題にも幅優先探索の使い道があり、おもしろかったです!




AtCoder版!蟻本(初級編)の記事リンクページはこちら
ebisuke33.hatenablog.com