座標圧縮

座標圧縮

座標圧縮 というアルゴリズムを使うと、効率的に問題を解くことができるケースがあります。

[問題]

２次元のマップがあり、何もない通り抜けのできる空間(.)と通り抜けのできない壁(#)が設定されています。

壁によって分断されている領域は何個あるでしょうか。

解法・ソースコード

この問題では、前後の行または列に 変化がない場合 その行または列を省いても、壁によって分断される 領域の個数 は変わりません。

まず、同じ行があったらその行を削除し、次に同じ列があったらその列を削除するという処理を行います。

[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
#---------- 入力例 ----------
# .が空間、#が壁
mp = '''...#....#.
...#....#.
...#....#.
######..#.
...#....#.
...#.....#
...#.....#
##########
...#.....#
...#.....#'''
#----------------------------

mp_compress = {}  # 縦と横を圧縮したデータ

print(' 【 圧縮前 】 ')
print(mp)
print()

# 縦を圧縮
lst = []    # 縦を圧縮したデータ
pre = ''    # １行前のデータ（初期化）
for line in mp.split():
    if pre != line:
        lst.append(line)
    pre = line
# 横を圧縮
pre = ''  # １列前のデータ（初期化）
w = 0
for col in range(len(lst[0])):  # 列ごとにループ
    row = [l[col] for l in lst] # 1列分のデータを取得
    line = ''.join(row)
    if pre != line:
        for y, s in enumerate(list(line)):
            mp_compress[w, y] = s
        w += 1
    pre = line

print(' 【 圧縮後 】 ')
for y in range(len(lst)):
    for x in range(w):
        print(mp_compress[x,y], end='')
    print()

[実行結果]

 【 圧縮前 】
...#....#.
...#....#.
...#....#.
######..#.
...#....#.
...#.....#
...#.....#
##########
...#.....#
...#.....#

 【 圧縮後 】
.#..#.
###.#.
.#..#.
.#...#
######
.#...#

問題なく座標が圧縮され、壁に分断されている領域の数も変わっていないことが確認できました。

次に、圧縮されたマップに対して分断されている領域のカウントを行います。

これは、まず壁ではない地点をみつけ、そこからつながっている部分を 壁（#） に置き換えるという操作を繰り返します。

一回の深さ優先探索で、始めの壁ではない地点からつながっている空間(.)が全て壁(#)に変わるので、深さ優先探索を行った回数 が解となります。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 深さ優先探索(Depth-First Search)
def dfs(x, y):
    global mp_compress
    # 今いるところを#に置き換え
    mp_compress[x, y] = '#'
    for dx, dy in [(1,0), (-1,0), (0,1), (0,-1)]:
        pos = (x + dx, y + dy)
        if pos in mp_compress and mp_compress[pos] == '.':
            dfs(pos[0], pos[1])
# 領域を数える
cnt = 0
for pos,v in mp_compress.items():
    if v == '.':
        dfs(pos[0], pos[1])
        cnt += 1
print('解：', cnt)

[実行結果]

解： 6

解は 6 となり、壁により分断されている空間が６つであることが確認できました。