ダイクストラ法＋ヒープキュー＋経路表示（最短経路問題）

ダイクストラ法＋ヒープキュー＋経路表示

前回記事では、ダイクストラ法 と ヒープキュー を使って最短経路問題の効率を上げて解きました。

今回は、さらに 最短経路 を表示します。

グラフは前回同様のものを使います。

[グラフ]

ソースコード

経路を表示するのはとても簡単です。

前回記事では ヒープキュー に コスト と 頂点名 を設定していましたが、さらに 経路 を設定するだけです。

heappush関数 の引数が３つになっています。（22行目、40行目）

（入力データの形式は前回記事と同様です）

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#---------- 入力例 ----------
nodes = {                                   # ノード情報
    'Start':{'edge':{'B':4, 'C':3},         # 隣の頂点までのコスト（頂点名:コスト）
             'cost':0},                     # 頂点Startまでの最小コスト
    'B':    {'edge':{'C':1, 'D':1, 'E':5},  # 隣の頂点までのコスト（頂点名:コスト）
             'cost':float('inf')},          # 頂点Bまでの最小コスト
    'C':    {'edge':{'F':2},                # 隣の頂点までのコスト（頂点名:コスト）
             'cost':float('inf')},          # 頂点Cまでの最小コスト
    'D':    {'edge':{'E':3},                # 隣の頂点までのコスト（頂点名:コスト）
             'cost':float('inf')},          # 頂点Dまでの最小コスト
    'E':    {'edge':{'Goal':2},             # 隣の頂点までのコスト（頂点名:コスト）
             'cost':float('inf')},          # 頂点Eまでの最小コスト
    'F':    {'edge':{'E':1, 'Goal':4},      # 隣の頂点までのコスト（頂点名:コスト）
             'cost':float('inf')},          # 頂点Fまでの最小コスト
    'Goal': {'edge':{},                     # 隣の頂点までのコスト（頂点名:コスト）
             'cost':float('inf')}           # 頂点Goalまでの最小コスト
}
#----------------------------
import heapq

q = []
heapq.heappush(q, (0, 'Start', 'Start')) # スタート位置である頂点の(コスト,頂点名、経路)をヒープキューに追加

# ダイクストラ法（最もコストの小さい頂点を順番に確認していく方法）
while len(q):       # キューがある限り実行
    # 最もコストが小さい頂点名をヒープキューから取得
    d = heapq.heappop(q) # コスト,頂点名,経路が返ってくる
    min_node_name = d[1] # 頂点名
    path = d[2]          # 経路
    if min_node_name == 'Goal':         # ゴール位置の頂点だった場合
        print('解：最小コストは', nodes['Goal']['cost'])    # 最小コストを表示して終了
        print('経路：', path)
        break
    # 最もコストが小さい頂点からの辺を繰り返しチェックする
    for dst, cost in nodes[min_node_name]['edge'].items():
        # 次の頂点までのコストが更新対象であれば更新
        if nodes[dst]['cost'] > nodes[min_node_name]['cost'] + cost:
            nodes[dst]['cost'] = nodes[min_node_name]['cost'] + cost
            # コストを更新した頂点の(コスト,頂点名,経路)をヒープキューに追加
            heapq.heappush(q, (nodes[dst]['cost'], dst, path + ' → ' + dst))

[実行結果]

解：最小コストは 8

経路： Start -> C -> F -> E -> Goal

最小コストの場合の、経路を表示 することができました。

ダイクストラ法＋ヒープキュー（最短経路問題）

ダイクストラ法＋ヒープキュー

前回記事では、ダイクストラ法 を使って最短経路問題を解きました。

今回は、ヒープキュー を使って処理をより効率的にしていきます。

グラフは前回同様のものを使います。

[グラフ]

ソースコード

ヒープキュー は、格納されているデータの中から 一番小さなもの を効率よく取り出せるキューです。

ダイクストラ法 の処理の中で、一番小さなコストの頂点を探すときに ヒープキュー（heapq） を使います。

（入力データの形式は前回記事と同様です）

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#---------- 入力例 ----------
nodes = {                                   # ノード情報
    'Start':{'edge':{'B':4, 'C':3},         # 隣の頂点までのコスト（頂点名:コスト）
             'cost':0},                     # 頂点Startまでの最小コスト
    'B':    {'edge':{'C':1, 'D':1, 'E':5},  # 隣の頂点までのコスト（頂点名:コスト）
             'cost':float('inf')},          # 頂点Bまでの最小コスト
    'C':    {'edge':{'F':2},                # 隣の頂点までのコスト（頂点名:コスト）
             'cost':float('inf')},          # 頂点Cまでの最小コスト
    'D':    {'edge':{'E':3},                # 隣の頂点までのコスト（頂点名:コスト）
             'cost':float('inf')},          # 頂点Dまでの最小コスト
    'E':    {'edge':{'Goal':2},             # 隣の頂点までのコスト（頂点名:コスト）
             'cost':float('inf')},          # 頂点Eまでの最小コスト
    'F':    {'edge':{'E':1, 'Goal':4},      # 隣の頂点までのコスト（頂点名:コスト）
             'cost':float('inf')},          # 頂点Fまでの最小コスト
    'Goal': {'edge':{},                     # 隣の頂点までのコスト（頂点名:コスト）
             'cost':float('inf')}           # 頂点Goalまでの最小コスト
}
#----------------------------
import heapq

q = []
heapq.heappush(q, (0, 'Start')) # スタート位置である頂点の(コスト,頂点名)をヒープキューに追加

# ダイクストラ法（最もコストの小さい頂点を順番に確認していく方法）
while len(q):       # キューがある限り実行
    # 最もコストが小さい頂点名をヒープキューから取得
    min_node_name = heapq.heappop(q)[1] # コストと頂点名が返ってくるので、頂点名だけ取得
    if min_node_name == 'Goal':         # ゴール位置の頂点だった場合
        print('解：最小コストは', nodes['Goal']['cost'])    # 最小コストを表示して終了
        break
    # 最もコストが小さい頂点からの辺を繰り返しチェックする
    for dst, cost in nodes[min_node_name]['edge'].items():
        # 次の頂点までのコストが更新対象であれば更新
        if nodes[dst]['cost'] > nodes[min_node_name]['cost'] + cost:
            nodes[dst]['cost'] = nodes[min_node_name]['cost'] + cost
            # コストを更新した頂点の(コスト,頂点名)をヒープキューに追加
            heapq.heappush(q, (nodes[dst]['cost'], dst))

[実行結果]

解：最小コストは 8

前回同様 頂点Start から 頂点Goal までの最小コストは 8 であることを導き出すことができました。

ヒープキュー を使うことにより、ソースコードがすっきりした感じがします。

また、最小コストの頂点取得の 検索効率があがった ので処理も高速化しているはずです。
（今回のグラフはシンプルすぎて効果を実感できないかもしれませんが・・・）

ダイクストラ法（最短経路問題）

ダイクストラ法

ダイクストラ法 は、最短経路問題 を解くアルゴリズムの１つです。

ダイクストラ法 には次のような特徴があります。

  • コストが最小になる頂点 を探しながら最短経路を求める。
  • マイナスの値 の場合は使えないが、ベルマンフォード法よりも高速に解を求めることができる。

次のようなグラフを考えてみます。

[グラフ]

ソースコード

ソースコードでは、グラフの情報を次の入力例のように定義してみます。

  • 頂点は名前（頂点名）をもち、それぞれの頂点は隣の頂点情報(edge)と自分のコスト(cost)情報を持っています。
  • 隣の頂点情報は、頂点名（辞書型データのキー）とそこに移動するためのコスト（辞書型データのバリュー）があり、複数存在することがあります。
  • 頂点自体がもっているコストは、そこに辿りつくためのコストであり、初期値としてはスタート地点が０、それ以外は無限大を設定しておきます。

ダイクストラ法 では、コストが最もコストが小さくなる頂点 を選択することを繰り返して探索する方法です。

一度チェックしたした頂点は チェック済み として、チェックしていない頂点 の中からコストが最も小さいものを順番に確認していきます。

最も小さいコストの頂点が複数ある場合は、そのうちどれか１つを選択してチェックしていきます。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#---------- 入力例 ----------
nodes = {                                   # ノード情報
    'Start':{'edge':{'B':4, 'C':3},         # 隣の頂点までのコスト（頂点名:コスト）
             'cost':0},                     # 頂点Startまでの最小コスト
    'B':    {'edge':{'C':1, 'D':1, 'E':5},  # 隣の頂点までのコスト（頂点名:コスト）
             'cost':float('inf')},          # 頂点Bまでの最小コスト
    'C':    {'edge':{'F':2},                # 隣の頂点までのコスト（頂点名:コスト）
             'cost':float('inf')},          # 頂点Cまでの最小コスト
    'D':    {'edge':{'E':3},                # 隣の頂点までのコスト（頂点名:コスト）
             'cost':float('inf')},          # 頂点Dまでの最小コスト
    'E':    {'edge':{'Goal':2},             # 隣の頂点までのコスト（頂点名:コスト）
             'cost':float('inf')},          # 頂点Eまでの最小コスト
    'F':    {'edge':{'E':1, 'Goal':4},      # 隣の頂点までのコスト（頂点名:コスト）
             'cost':float('inf')},          # 頂点Fまでの最小コスト
    'Goal': {'edge':{},                     # 隣の頂点までのコスト（頂点名:コスト）
             'cost':float('inf')}           # 頂点Goalまでの最小コスト
}
#----------------------------
# ダイクストラ法（最もコストの小さい頂点を順番に確認していく方法）
while len(nodes):       # 未チェックの頂点がある限り実行
    # 最もコストが小さい頂点を探す
    min_cost = min([node_info['cost'] for src, node_info in nodes.items()])
    for name, node_info in nodes.items():
        if node_info['cost'] == min_cost:
            min_node_name = name    # 最もコストが小さい頂点名を取得
            break

    # 最もコストが小さい頂点からの辺を繰り返しチェックする
    for dst, cost in node_info['edge'].items():
        # 次の頂点が未チェック かつ 次の頂点までのコストが更新対象であれば更新
        if dst in nodes and nodes[dst]['cost'] > nodes[min_node_name]['cost'] + cost:
            nodes[dst]['cost'] = nodes[min_node_name]['cost'] + cost

    if min_node_name == 'Goal': # チェックした頂点が'Goal'の場合
        print('解：最小コストは', nodes['Goal']['cost'])    # 最小コストを表示して終了
        break

    del nodes[min_node_name]    # チェックが終わった頂点は削除(チェック済みとする)

[実行結果]

解：最小コストは 8

頂点Start から 頂点Goal までの最小コストは 8 であることを導き出すことができました。

ベルマンフォード法（最短経路問題）

ベルマンフォード法

ベルマンフォード法 は、最短経路問題 を解くアルゴリズムの１つです。

ベルマンフォード法 には次のような特徴があります。

  • 頂点を結んだ 辺の重み（コスト）を更新しながら最短経路を求めます。
  • 辺の重み（コスト）が マイナス の場合でも解くことができます。

次のようなグラフを考えてみます。

[グラフ]

各頂点におけるスタート地点からのコストを求めるにあたり、設定した初期値から辺の重みを使って順に更新する作業を繰り返し、それ以上更新できなくなったら処理を終了します。

ソースコード

ソースコードでは、グラフの情報を次の入力例のように定義してみます。

  • 頂点は名前（頂点名）をもち、それぞれの頂点は隣の頂点情報(edge)と自分のコスト(cost)情報を持っています。
  • 隣の頂点情報は、頂点名（辞書型データのキー）とそこに移動するためのコスト（辞書型データのバリュー）があり、複数存在することがあります。
  • 頂点自体がもっているコストは、そこに辿りつくためのコストであり、初期値としてはスタート地点が０、それ以外は無限大を設定しておきます。

ベルマンフォード法 では、次のような手順で頂点のコスト情報を更新していきます。

  1. 辺を１つ選ぶ。
  2. 選んだ辺のコストを使って、両端の頂点のコストを更新する。
    （コストが小さい頂点に辺のコストを加算した値が、もう一方の頂点のコストよりも小さい場合、更新する）
  3. 全ての頂点に対して、コストが更新されなくなるまで上記の1～2を繰り返す。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#---------- 入力例 ----------
nodes = {                                   # ノード情報
    'Start':{'edge':{'B':4, 'C':3},         # 隣の頂点までのコスト（頂点名:コスト）
             'cost':0},                     # 頂点Startまでの最小コスト
    'B':    {'edge':{'C':1, 'D':1, 'E':5},  # 隣の頂点までのコスト（頂点名:コスト）
             'cost':float('inf')},          # 頂点Bまでの最小コスト
    'C':    {'edge':{'F':2},                # 隣の頂点までのコスト（頂点名:コスト）
             'cost':float('inf')},          # 頂点Cまでの最小コスト
    'D':    {'edge':{'E':3},                # 隣の頂点までのコスト（頂点名:コスト）
             'cost':float('inf')},          # 頂点Dまでの最小コスト
    'E':    {'edge':{'Goal':2},             # 隣の頂点までのコスト（頂点名:コスト）
             'cost':float('inf')},          # 頂点Eまでの最小コスト
    'F':    {'edge':{'E':1, 'Goal':4},      # 隣の頂点までのコスト（頂点名:コスト）
             'cost':float('inf')},          # 頂点Fまでの最小コスト
    'Goal': {'edge':{},                     # 隣の頂点までのコスト（頂点名:コスト）
             'cost':float('inf')}           # 頂点Goalまでの最小コスト
}
#----------------------------
# ベルマンフォード法（辺の重みに注目する方法）
is_updated = True                           # 更新フラグを立てる
while is_updated:                           # 頂点が更新されなくなるまで実行
    is_updated = False                      # 更新フラグを落とす
    for src, node_info in nodes.items():    # 頂点をすべてチェック
        for dst, cost in node_info['edge'].items():             # その頂点からの辺をすべてチェック
            if nodes[src]['cost'] + cost < nodes[dst]['cost']:  # 頂点のコスト＋辺のコストが、次の頂点のコストより小さい場合
                nodes[dst]['cost'] = nodes[src]['cost'] + cost  # 次の頂点のコストを更新
                is_updated = True                               # 更新フラグをたてる
print('解：最小コストは', nodes['Goal']['cost'])

[実行結果]

解：最小コストは 8

頂点Start から 頂点Goal までの最小コストは 8 であることを導き出すことができました。

ベルマンフォード法の注意点

辺のコスト というのは 時間 や 料金、距離 などが対応すると考えられます。

これらはいずれもプラスの値ですが、もしマイナスの値であってもベルマンフォード法は有効です。

ただし、マイナスの値でループ しているような 経路（閉路） がある場合は、そのループを回り続けるといくらでもコストが小さくなってしまうため ベルマンフォード法 では解くことができません。

グラフ（辞書型編）

グラフ（辞書型編）

グラフ は、対象物の関係性 を表します。

グラフ を使うと、友人関係・鉄道路線・タスクの依存関係など、さまざまな関係性を表現できます。

関係性を グラフ で表すと、問題を抽象的に考えることができるというメリットがあります。

問題

次のような問題があります。

[問題]

頂点数がＮ個、辺数がＭ本であるような無向グラフ（辺の向きがないグラフ）があります。

頂点は隣接する頂点の情報（複数）を持っています。

それぞれの頂点は色の情報をもっており、色の情報は塗り替えることができます。

クエリ―は２種類あり下記のような操作を行います。

　クエリ―１：1 aという形式で情報が与えられ、頂点aに隣接する頂点 の色が 頂点aの色 に塗り変えられます。
　
　クエリ―２：2 a bという形式で情報が与えられ、頂点a の色が 色b に塗り替えられます。

[条件]

・頂点数Ｎは1以上200以下の整数

・変数ＭはＮ（Ｎ－１）／２以下の整数

・クエリ―数Ｑは1以上200以下の整数

解法・ソースコード

頂点と辺、色の情報を辞書型の変数で管理します。

辞書型のキーには 頂点のID を設定し、辞書型の値として 色情報と隣接する頂点 の情報を辞書型データとして設定します。

クエリ―ごとに各頂点の色情報を更新し、最後に各頂点の色情報を表示しています。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#---------- 入力例 ----------
# ノード情報
nodes = {
    1:{'color':5,       # 色情報（初期）
       'edge':[2]},     # 隣接ノード（１→２）
    2:{'color':10,      # 色情報（初期）
       'edge':[1,3]},   # 隣接ノード（２→１、２→３）
    3:{'color':15,      # 色情報（初期）
       'edge':[2]},     # 隣接ノード（３→２）
}
# クエリ―情報
querys = [(1, 2),
          (2, 1, 20),
          (1, 1)]
#----------------------------
# 各ノードの色情報を表示する
def show_color():
    for k,v in nodes.items():
        print('  node[{}]: color[{}]'.format(k, v['color']))

print('【初期のカラー情報】')
show_color()
print(' -------')

for query in querys:
    print('クエリ―', query)
    node = nodes[query[1]]          # ノードを選択
    if query[0] == 1:               # クエリ―がタイプ１の場合
        for e in node['edge']:      # 選択ノードに隣接する各ノードの色を更新
            nodes[e]['color'] = node['color']
    else:                           # クエリ―がタイプ２の場合
        node['color'] = query[2]    # 選択ノードの色を更新
    print(' (カラー情報)')
    show_color()
    print(' -------')

print('【解：カラー情報】')
show_color()

[実行結果]

【初期のカラー情報】
  node[1]: color[5]
  node[2]: color[10]
  node[3]: color[15]
 -------
クエリ― (1, 2)
 (カラー情報)
  node[1]: color[10]
  node[2]: color[10]
  node[3]: color[10]
 -------
クエリ― (2, 1, 20)
 (カラー情報)
  node[1]: color[20]
  node[2]: color[10]
  node[3]: color[10]
 -------
クエリ― (1, 1)
 (カラー情報)
  node[1]: color[20]
  node[2]: color[20]
  node[3]: color[10]
 -------
【解：カラー情報】
  node[1]: color[20]
  node[2]: color[20]
  node[3]: color[10]

１番目のクエリ―により、頂点２に隣接する全ての頂点の色が10に塗り替えられます。

２番目のクエリ―により、頂点１の色が色20に塗り替えられます。

３番目のクエリ―により、頂点１に隣接する全ての色が20に塗り替えられます。

最終的には、頂点１の色が20、頂点２の色が20、頂点３の色が10になっていることが確認できます。

バケット（辞書型編）

バケット（辞書型編）

前回は、配列 を使ってバケットの手法を実現しましたか、今回は 辞書型 を使ってバケットの手法を実現してみます。

問題は前回と同様のものを使います。

[問題]

Ｎ個 の正の整数があります。

この中に含まれる数値の種類の個数を求めて下さい。

[条件]

・各数字は、1以上10以下の整数

解法・ソースコード

前回は配列のインデックスと入力の数字を対応させました。

辞書型では、入力の数字を 辞書型のキー とし、数字の個数を 辞書型のバリュー（値） としてみます。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
#---------- 入力例 ----------
lst = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9]
#----------------------------
bucket = {}             # バケットを辞書型として定義
# 入力リストからバケットを作成
for l in lst:
    if l in bucket:     # バケットにすでにキーがある場合
        bucket[l] += 1  # カウントアップ
    else:               # バケットにまだキーがない場合
        bucket[l] = 1   # １つ目としてバケット（辞書型）に登録

print('バケット：', bucket)
print('解（種類の個数）：', len(bucket))

前回配列を使ったときとコード量はあまり変わりませんが、配列では固定のエリア（数字の種類分の配列）を確保する必要があり未使用になる可能性もあったので、辞書型の方が無駄なく実装できているような気がします。

バケット： {3: 2, 1: 2, 4: 1, 5: 3, 9: 2, 2: 1, 6: 1, 8: 1}

解（種類の個数）： 8

解は 8 となり、前回記事と同様に入力の数字の種類が 8種類 であることが確認できました。

バケット（配列編）

バケット（配列編）

バケット はあらかじめデータがとりうる値を、すべての容器(バケット)に順番どおりに並べ用意しておくアルゴリズムです。

バケット を使うと次のようなさまざまな問題に簡単に解を出すことができます。

  • 配列にある値が含まれるかどうかを判定できる。
  • 配列に含まれる値が何種類あるかわかる。
  • 配列の要素がすべて異なるかどうかを判定できる。

[問題]

Ｎ個の正の整数があります。

この中に含まれる数値の種類の個数を求めて下さい。

[条件]

・各数字は、1以上10以下の整数

解法・ソースコード

数字の範囲は10以下なので、サイズが11の配列を準備します。（配列のインデックスが0から10の整数を表す）

次に入力の数字ごとに配列に1を設定していきます。（その数字が存在したことを表す）

最終的にこの配列の合計値が、数値の種類の個数を表すことになります。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
#---------- 入力例 ----------
lst = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9]
#----------------------------
# バケット（全体を0で初初期化）範囲 0～10
bucket = [0] * 11

# 入力リストからバケットを作成
for l in lst:
    bucket[l] = 1

print('バケット：', bucket)
print('解（数値の種類）：', sum(bucket))

[実行結果]

バケット： [0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0]

解（種類の個数）： 8

解は 8 となり、入力の数字の種類が 8種類 であることが確認できました。

二次元配列でマップ問題を解く

二次元配列でマップ問題を解く

次のような問題を考えます。

[問題]

長方形状のマップデータ（文字列）が与えられます。

１マスのデータは'#'が爆弾を表し、'.'は何もない空間（空きマス）を表します。

空きマスの上下左右および斜めの８方向に隣接しているマスの中に

爆弾のあるマスが何個あるかを調べて、その数を空きマス'.'に置き換えて

長方形状のマップを出力してください。

[条件]

・マップの縦幅と横幅は１以上かつ５０以下です。

・１マスのデータは'#'（爆弾）または'.'（何もない空間）のみです。

解法・ソースコード

長方形のマップを表すために、str型の変数からなるlistを活用します。

長方形状のマップを上からy番目、左からx番目のマスを(x, y)と表します。

入力の文字列データを１マスずつの２次元配列（２次元リスト）に設定します。（14行目）

この問題では、各空きマス(x, y)に対して、その周囲８マスにある爆弾の個数を数えます。

マス(x, y)の周囲８マスは (x+1, y)、(x-1, y)、(x, y+1)、(x, y-1)、(x+1, y+1)、(x+1, y-1)、(x-1, y+1)、(x-1, y-1) と表すことができます。

これらのマスを調べるために、周囲８方向に隣接するマスとの座標の差分値を表す配列を用意しておくと便利です。（17行目）

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#---------- 入力例 ----------
# .が空間、#が爆弾
mp = '''........
..#...#.
........
....#...
.....#..'''
#----------------------------
print('【 元のマップ 】 ')
print(mp)
print()

# 入力データを二次元配列に設定
res = [list(line) for line in mp.split('\n')]

# 隣接８方向への相対位置を定義
dxy = [(1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (1, -1), (-1, 1), (-1, -1)]

for y, row in enumerate(res):           # 縦ループ
    for x, s in enumerate(row):         # 横ループ
        if s == '.':                    # 空きマスの場合
            res[y][x] = 0               # 初期化（周囲の爆弾数）
            for dx, dy in dxy:          # ８方向をループ
                x1, y1 = x + dx, y + dy # マスの周囲をx1,y1とする
                # マップ外の場合はパス
                if x1 < 0 or x1 > len(row) - 1 or y1 < 0 or y1 > len(res) - 1:
                    pass
                elif res[y1][x1] == '#':    # 周囲が爆弾'#'の場合
                    res[y][x] += 1          # 爆弾数カウントアップ

print('【 隣接する爆弾の個数を表示したマップ 】 ')
for row in res:
    print(*row, sep='')

[実行結果]

【 元のマップ 】 
........
..#...#.
........
....#...
.....#..

【 隣接する爆弾の個数を表示したマップ 】 
01110111
01#101#1
01121211
0001#210
00012#10

空きマスの周辺にある爆弾数をカウントしてマップを表示することができました。

全探索

全探索

次のような問題を考えます。

[問題]

500円玉がＡ枚、100円玉がＢ枚、50円玉がＣ枚あります。

これらの硬貨の中から何枚かを選び、合計金額をちょうどＸ円にする方法は

何通りありますか。

[条件]

・それぞれの枚数Ａ、Ｂ、Ｃは0以上かつ50以下の整数。
・目標金額Ｘは50以上かつ20000以下の50の倍数。
・それぞれの枚数の合計（Ａ＋Ｂ＋Ｃ）は1以上。

解法・ソースコード

この問題は、各硬貨の枚数分それぞれループを回して目標の金額になるかどうかをチェックすることで解くことができます。（三重ループしながら金額をチェック）

硬貨は 0枚 の時があるので、ループ回数は各硬貨の 枚数分 + 1 となることに注意してください。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#---------- 入力例 ----------
a = 2   # 500円玉の枚数
b = 2   # 100円玉の枚数
c = 2   # 50円玉の枚数
x = 100 # 目標金額
#----------------------------
res = 0     # 何通りあるかという解
# 全探索
for a1 in range(0, a + 1):          # 500円玉の枚数分ループ
    for b1 in range(0, b + 1):      # 100円玉の枚数分ループ
        for c1 in range(0, c + 1):  # 50円玉の枚数分ループ
            # 合計金額がＸ円に一致した場合
            if 500 * a1 + 100 * b1 + 50 * c1 == x:
                # それぞれの硬貨の枚数を出力
                print(f'500円{a1}枚、100円{b1}枚、50円{c1}枚')
                res += 1            # 解をカウントアップ
print('解：', res)

[実行結果]

500円0枚、100円0枚、50円2枚
500円0枚、100円1枚、50円0枚
解： 2

解は ２通り あることが分かりました。

硬貨の組み合わせは、合計金額が一致した場合のそれぞれの硬貨数を表示することで確認できます。

反転

反転問題

次のような問題があります。

[問題]

Ｎ頭の牛が１列に並んでいて、それぞれの牛は前か後ろのいずれかを向いています。

農夫は全ての牛を前向きにするために、牛を回転する機械を買うことにしました。

この機会は購入時に 数Ｋ を設定する必要があり、１回の操作で Ｋ頭の連続する

牛 の向きを反転させることができます。

全ての牛を前向きにするために必要な最小の 操作回数Ｍ と、それを達成する

最小のＫ を求めてください。

解法・ソースコード

まず、一番左端の牛に注目します。この牛を含む区間は１つしかありません。

したがって、この牛が前を向いているならば、その区間は反転させる必要がありません。

逆に、この牛が後ろを向いているならば、その区間は反転させる必要があります。

そして、これ以降はこの１番左の区間は考える必要がなくなります。

これを繰り返し行うことによって、必要な最小の反転回数を求めることができます。

また、計算量 を落とすためにリストfを定義し、区間を反転させた場合は１そうでない場合は０を設定し、その合計値が奇数である場合は最初の向きとは逆に、そうでなければ最初の向きのままとなっていることを確認しています。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#---------- 入力例 ----------
cows = 'BBFBFBB'    # F:前向き、B:後ろ向き
#----------------------------
n = len(cows)   # 牛の頭数
k = 1           # 求める最小の牛を回転させる連続頭数（初期化）
m = n           # 求める最小の操作回数（初期化）

# 牛を回転させる連続頭数ｋを固定した時の最小操作回数を求める
# 解が存在しない場合は -1 を返す
def calc(k):
    # 区間[i, i + k - 1 ]を回転させたかどうか
    f = [0 for _ in range(n)]
    res = 0         # 操作回数
    total = 0       # リストfの和
    for i in range(n - k + 1):
        if (dir[i] + total) % 2 != 0:   # 先頭の牛が後ろを向いている場合
            # 回転操作を行う
            res += 1
            f[i] = 1
        total += f[i]
        if i - k + 1 >= 0:
            total -= f[i - k + 1]
    # 残りの牛が前を向いているかどうかチェック
    for i in range(n - k + 1, n):
        if (dir[i] + total) % 2 != 0:
            return -1
        if i - k + 1 >= 0:
            total -= f[i - k + 1]
    return res

# 牛の方向を0(F：前向き),1(B：後ろ向き)に変換
dir = [0 if x == 'F' else 1 for x in list(cows)]

for i in range(1, n + 1):   # 牛の頭数分ループする
    print(i, '頭回転させる機械の場合')
    x = calc(i)
    if x >= 0 and m > x:    # 牛を全部前向きにでき、かつ操作回数がより少ない場合
        print(x, '回操作で牛を全部前向きにできる。')
        m = x       # 最小の操作回数を更新
        k = i       # 回転させる最小の連続頭数を更新
    else:
        print('牛の向きを全部前向きにするとはできない。')
    print()

print(f'解：回転させる最小の連続頭数={k}　最小の操作回数={m}')

[実行結果]

1 頭回転させる機械の場合
5 回操作で牛を全部前向きにできる。

2 頭回転させる機械の場合
牛の向きを全部前向きにするとはできない。

3 頭回転させる機械の場合
3 回操作で牛を全部前向きにできる。

4 頭回転させる機械の場合
牛の向きを全部前向きにするとはできない。

5 頭回転させる機械の場合
牛の向きを全部前向きにするとはできない。

6 頭回転させる機械の場合
牛の向きを全部前向きにするとはできない。

7 頭回転させる機械の場合
牛の向きを全部前向きにするとはできない。

解：回転させる最小の連続頭数=3　最小の操作回数=3

牛を連続で ３頭回す機械<.b> を購入すれば、最小３回の操作</ > で牛を全部前向きにできることが分かりました。

© 2026 Playing with Python All Rights Reserved.
Theme by hipaper