ボードゲーム

問題

$1$ から $N$ までの整数が一個ずつ書かれた $ N \times N $ のマス目 $P$ が与えられます。

次の２種類の操作を繰り返すことで、すべての $k$ に対して「整数 $k$ が上から $k$ 行目・左から $k$ 列目のマスに存在する」ようにするためには、最小何回の操作が必要ですか。

🔹隣接する２つの行を交換する。
🔹隣接する２つの列を交換する。

[制約]
🔹$ 2 \leqq N \leqq 100 $

解き方・ソースコード

まず行の操作と列の操作を分解できないかどうかを考えます。

$i$ 行目に書かれた唯一の整数を $X_i$、$j$ 列目に書かれた唯一の整数を $Y_j$ とすると、以下の２点が成り立ちます。

🔹$i$行目と $i+1$ 行目を交換した場合： $X_i$ と $X_{i+1}$ のみが入れ替わり、$Y$ は不変
🔹$j$列目と $j+1$ 列目目を交換した場合： $Y_j$ と $Y_{j+1}$ のみが入れ替わり、$X$ は不変

このことは「行に対する操作」と「列に対する操作」を分けてよいことを意味しています。

また、目的通りの盤面になっていることと、$X=[1,2,3,4]$ かつ $Y=[1,2,3,4]$ になっていることはまったく同じです。

したがって、入力例１の最小操作回数は

🔹値１：最小何回の「隣接要素の交換」で、配列 $X$ を $[1,2,3,4]$ にできるか。
🔹値２：最小何回の「隣接要素の交換」で、配列 $Y$ を $[1,2,3,4]$ にできるか。

の総和となります。

[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
#-------- 入力例１ ---------
N = 4                       # 整数の数
P = [
    [0, 0, 2, 0],
    [3, 0, 0, 0],
    [0, 0, 0, 4],
    [0, 1, 0, 0],
]
#---------------------------
# 「交換数を求める問題」2 つに分解する
X = [ None ] * N
Y = [ None ] * N
for i in range(N):
    for j in range(N):
        if P[i][j] != 0:
            X[i] = P[i][j]
            Y[j] = P[i][j]

# 交換数を求める関数
def inversion(A):
    answer = 0
    for i in range(len(A)):
        for j in range(i + 1, len(A)):
            if A[i] > A[j]:
                answer += 1
    return answer

# 答えを出力
print('解：', inversion(X) + inversion(Y))

[実行結果]

解： 5

最小操作回数が５回であることが確認できました。