n x n 이진 행렬이 있다고 가정합니다. 한 단계에서 인접한 두 행을 선택하고 교체하는 것과 같은 작업을 수행할 수 있습니다. 행렬의 주요 대각선 위의 모든 노드가 0이 되도록 필요한 최소 스왑 수를 계산해야 합니다. 이러한 솔루션이 없으면 -1을 반환합니다.
따라서 입력이 다음과 같으면
| 0 | 1 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
출력은 2가 됩니다. -
이 문제를 해결하기 위해 다음 단계를 따릅니다.
-
n :=행렬의 행 수
-
m :=크기가 n인 배열을 만들고 n으로 채움
-
범위 0에서 n - 1에 있는 i에 대해 수행
-
n-1 ~ 0 범위의 j에 대해 1 감소, 수행
-
행렬[i, j]가 1과 같으면
-
m[i] :=n-j-1
-
루프에서 나오다
-
-
-
-
t :=0, ans :=0
-
범위 0에서 n - 1에 있는 i에 대해 수행
-
t :=t + 1
-
플래그 :=거짓
-
i에서 n - 1 사이의 j에 대해 수행
-
m[j]>=n-t이면
-
ans :=ans + j-i
-
플래그 :=참
-
루프에서 나오다
-
-
-
플래그가 거짓이면
-
반환 -1
-
-
m[인덱스 i+1에서 j로] 업데이트 m[인덱스 i에서 j-1로]
-
-
반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
def solve(matrix): n = len(matrix) m = [n] * n for i in range(n): for j in range(n-1,-1,-1): if matrix[i][j] == 1: m[i] = n-j-1 break t,ans = 0,0 for i in range(n): t += 1 flag = False for j in range(i,n): if m[j] >= n-t: ans += j-i flag = True break if not flag: return -1 m[i+1:j+1] = m[i:j] return ans matrix = [[0,1,0],[0,1,1],[1,0,0]] print(solve(matrix))
입력
[[0,1,0],[0,1,1],[1,0,0]]
출력
2