n × n 크기의 이진 행렬(binary matrix)이 있다고 가정해 보겠습니다. 이 행렬에는 한 가지 연산만 허용되는데, 바로 인접한 두 행을 선택해 서로 맞바꾸는(스왑) 것입니다. 우리가 구해야 할 값은 주 대각선(major diagonal) 위쪽 영역의 모든 원소가 0이 되도록 만들 때 필요한 최소 스왑 횟수입니다. 만약 어떻게 행을 배치하더라도 조건을 만족할 수 없다면 -1을 반환해야 합니다.
문제 예시
예를 들어 입력이 다음과 같다고 해봅시다.
| 0 | 1 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
이 경우 출력은 2입니다. 두 번의 인접 행 스왑만으로 주 대각선 위의 모든 원소를 0으로 만들 수 있기 때문입니다.
해결 접근 방식
핵심 아이디어는 각 행마다 가장 오른쪽에 있는 1의 위치를 기준으로 삼는 것입니다. 주 대각선 위가 모두 0이 되려면 i번째 행의 마지막 1은 반드시 (n-1-i)번째 열 또는 그보다 오른쪽에 있어야 합니다.
알고리즘은 다음 단계로 진행됩니다.
- n := 행렬의 행 개수
- m := 크기가 n인 배열을 만들고 모든 값을 n으로 초기화
- i를 0부터 n-1까지 반복:
- j를 n-1부터 0까지 감소시키며 반복:
- matrix[i][j]가 1이면
- m[i] := n-j-1 (마지막 1이 오른쪽 끝에서 얼마나 떨어져 있는지 저장)
- 내부 반복 종료
- matrix[i][j]가 1이면
- j를 n-1부터 0까지 감소시키며 반복:
- t := 0, ans := 0으로 초기화
- i를 0부터 n-1까지 반복:
- t := t + 1
- flag := False
- j를 i부터 n-1까지 반복:
- m[j] >= n-t이면
- ans := ans + (j-i) — 해당 행을 앞당기는 데 필요한 스왑 횟수 누적
- flag := True
- 반복 종료
- m[j] >= n-t이면
- flag가 False면 return -1 (조건을 만족하는 행이 없음)
- m[i+1..j] 구간을 m[i..j-1] 값으로 갱신 (행을 한 칸씩 앞으로 당김)
- ans 반환
Python 구현 예제
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
동작 원리 정리
이 알고리즘은 그리디(greedy) 전략을 사용합니다. 각 위치 i에 대해, 현재 필요한 조건(마지막 1의 위치가 n-t 이상)을 만족하는 첫 번째 행을 찾아 앞으로 당깁니다. 이때 중간에 있는 행들은 자연스럽게 한 칸씩 뒤로 밀리며, 밀린 횟수만큼 스왑 비용이 누적됩니다. 시간 복잡도는 O(n²)로, n × n 행렬의 모든 경우를 효율적으로 처리할 수 있습니다.