Zenn
😽

正方形の二次配列を渦状に取得する

2025/01/19に公開
Python
アルゴリズム
tech

24新卒のDaikiです。
昔の記事をzennにまとめたいので昔書いた記事をこちらに移動します。

問題

正方形の二次配列が存在するとします。
例.)

array = [
    [1, 2, 3, 4]
    [12, 13, 14, 5]
    [11, 16, 15, 6]
    [10, 9, 8, 7]
]

この 縦x横の二次配列を渦状に一つ一つの要素を渡り、一次配列を取得してください。(Time ComplexityはO(n))

出力例
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]

考え方

1. 少し視点を変えて見てみる

１つ目の画像をみるとわかりやすいかも知れません。
渦巻状に取得はするものの、そこで少し視点を変えて問題に取り組んでみると外側の四角と内側の四角に分けることができます。

次にこの四角を迂回するにあたって、pointerが2つ（rowとcolumn用）あると考えてください。

このpointer２つを渦状に取得させるために考慮する点が１つあります。
それは、二重計上(double counting)の制御です。

補足：
ここでは、rowは横列、columnは縦列を指しているます。
二重計上(double counting) は簡潔に言いますと、処理にあたって同じ要素が被ってしまうことです。

2. 二重計上の制御

次の画像をご覧ください。

こうすることによってお互いに境界線を作ることができ、また二重計上も防ぐことができるので効率の良い解き方になってくると思います。

補足:
SC, EC, SR, ERとは？:
SCがcolumnのはじめ、ECがcolumnの終わり
SRがrowのはじめ、ERがrowの終わり
となっています。

3.　一連の処理の流れ(外側)

まず、top row([1, 2, 3, 4])をcolumn用のpointerで取得します。

サンプルコード：

   for col in range(sc, ec + 1):
       result.append(array[sr][col])

次に、ECが指しているcolumnをERまでrow用のpointerで取得します。(ここでは、[5, 6, 7]ですね。）

サンプルコード：

   for row in range(sr + 1, er + 1):
       result.append(array[row][ec])

そして、botton row([10, 9, 8])を逆方向にcolumn用のpointerで取得します。
ここは、reverseを使って逆方向のloopを実装します。
サンプルコード：

   for col in reversed(range(sc, ec)):
       result.append(array[er][col])

最後に、２行目の[12]と３行目の[11]を取得したいのでSR+1 ~ ER区間で逆方向にrow用のpointerで取得します。
ここも、reverseを使います。
サンプルコード：

   for row in reversed(range(sr + 1, er)):
       result.append(array[row][sr])

これで、やっと外側の四角の要素を全て渦状に取得できました。

4.　一連の処理の流れ(内側)

次は、内側の四角です。

でも、このまま処理を同じように回すとhard codingになってしまいます。
なので、SRとSCを１つ足して内側に寄せます。また、ECとERを１つ足して内側に寄せることによって1~5で作ったものを再利用することができます。

内側の正方形の処理

sr += 1 
er -= 1
sc += 1
ec -= 1

top row([13, 14])をcolumn用のpointerで取得します
こちらも同様にloopする。
ECが指しているcolumnをERまでrow用のpointerで取得します。(ここでは、[15]ですね。）

bottom row([16])を逆方向にcolumn用のpointerで取得します。
ここは、reverseを使って逆方向のloopを実装します。

最後に、SRがERと等しくなるのでrangeが０になり何も取得できないようになります。

完成コード:

def spiral_traverse(array):
	result = []
	sr, er = 0, len(array) - 1
	sc, ec = 0, len(array[0]) - 1
	
	while sr <= er and sc <= ec:
		for col in range(sc, ec + 1):
			result.append(array[sr][col])
			
		for row in range(sr + 1, er + 1):
			result.append(array[row][ec])
			
		for col in reversed(range(sc, ec)):
			result.append(array[er][col])
			
		for row in reversed(range(sr + 1, er)):
			result.append(array[row][sr])
			
		sr += 1 
		er -= 1
		sc += 1
		ec -= 1
		
	return result

その他のやり方

上記の方法より効率的な方法を紹介します。

def get_n_to_i_j(N: int):
    def n_to_i_j(n: int):
        try:
            d = int(n / (2 * (N + (N ** 2 - n) ** 0.5)))
            q, r = divmod(n - 4 * d * (N - d), N - 1 - 2 * d)
            if q == 0:
                i = d
                j = d + r
            elif q == 1:
                i = d + r
                j = N - d - 1
            elif q == 2:
                i = N - d - 1
                j = N - d - r - 1
            elif q == 3:
                i = N - d - r - 1
                j = d
        except ZeroDivisionError:
            i = j = N // 2
        return i, j
    return n_to_i_j

終わりに

あくまで、１つの考え方なので、他にも解答方法はいくつもあります。例えば、再帰法を使った処理など。
読んでくださりありがとうございました。

Discussion