グラフ（辞書型編）

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

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

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

問題

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

[問題]

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

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

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

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

　クエリ―１：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> を購入すれば、最小３回の操作</ > で牛を全部前向きにできることが分かりました。