n×n 크기의 행렬이 하나 주어지며, 행렬의 값은 0부터 n 사이입니다. 이때 0은 아직 채워지지 않은 빈 칸을 의미합니다. 우리가 해야 할 일은 빈 칸들을 적절히 채워 각 행과 각 열마다 1부터 n까지의 모든 숫자가 정확히 한 번씩 등장하도록 만들 수 있는지 확인하는 것입니다.
예를 들어, 입력이 다음과 같다고 가정해 보겠습니다.
| 0 | 0 | 2 |
| 2 | 0 | 1 |
| 1 | 2 | 3 |
이 경우 출력은 True가 됩니다. 다음과 같이 행렬을 완성할 수 있기 때문입니다.
| 3 | 1 | 2 |
| 2 | 3 | 1 |
| 1 | 2 | 3 |
해결 접근 방식: 백트래킹
이 문제는 스도쿠(Sudoku) 퍼즐과 매우 유사하며, 백트래킹(Backtracking) 기법을 사용하면 효과적으로 해결할 수 있습니다. 핵심 아이디어는 빈 칸을 하나 찾아 가능한 숫자를 차례대로 넣어보고, 해당 값으로 진행이 불가능하면 이전 상태로 되돌아가 다른 값을 시도하는 것입니다.
알고리즘 단계
- find_empty_cell() 함수 정의 — 행렬과 n을 인자로 받습니다.
- i를 0부터 n-1까지, j를 0부터 n-1까지 반복하며 탐색합니다.
- matrix[i][j]가 0인 첫 번째 위치를 발견하면 (i, j)를 반환합니다.
- 모든 칸을 확인한 후에도 빈 칸이 없다면 (-1, -1)을 반환합니다.
- is_feasible() 함수 정의 — 행렬, i, j, x를 인자로 받아 해당 위치에 x를 놓을 수 있는지 검사합니다.
- x가 이미 i번째 행에 존재하면 False를 반환합니다.
- x가 이미 j번째 열에 존재하면 False를 반환합니다.
- 두 조건을 모두 통과하면 True를 반환합니다.
- is_complete() 함수 정의 — 행렬과 n을 인자로 받아 완성 여부를 검사합니다.
- 각 행에 중복된 요소가 있다면 False를 반환합니다.
- 각 열에 중복된 요소가 있다면 False를 반환합니다.
- 모든 검사를 통과하면 True를 반환합니다.
- 메인 메서드(solve)에서 다음을 수행합니다.
- n := 행렬의 행 개수
- (i, j) = find_empty_cell(matrix, n)
- (i, j)가 (-1, -1)과 같다면 더 이상 빈 칸이 없다는 뜻입니다.
- is_complete(matrix, n)이 참이면 True를 반환합니다.
- 그렇지 않으면 False를 반환합니다.
- x를 1부터 n까지 반복합니다.
- is_feasible(matrix, i, j, x)가 참이면 matrix[i][j] := x로 설정합니다.
- solve(matrix)의 재귀 호출 결과가 참이면 True를 반환합니다.
- 실패했다면 matrix[i][j] := 0으로 되돌려 다른 값을 시도합니다(백트래킹).
- 모든 시도가 실패하면 False를 반환합니다.
Python 구현 예제
아래 구현을 통해 동작 방식을 더 잘 이해할 수 있습니다.
class Solution:
def solve(self, matrix):
n = len(matrix)
def find_empty_cell(matrix, n):
for i in range(n):
for j in range(n):
if matrix[i][j] == 0:
return (i, j)
return (-1, -1)
def is_feasible(matrix, i, j, x):
if x in matrix[i]:
return False
if x in [row[j] for row in matrix]:
return False
return True
def is_complete(matrix, n):
for row in matrix:
if set(row) != set(range(1, n + 1)):
return False
for col in range(n):
if set(row[col] for row in matrix) != set(range(1, n + 1)):
return False
return True
(i, j) = find_empty_cell(matrix, n)
if (i, j) == (-1, -1):
if is_complete(matrix, n):
return True
else:
return False
for x in range(1, n + 1):
if is_feasible(matrix, i, j, x):
matrix[i][j] = x
if self.solve(matrix):
return True
matrix[i][j] = 0
return False
ob = Solution()
matrix = [
[0, 0, 2],
[2, 0, 1],
[1, 2, 3]
]
print(ob.solve(matrix))
입력
matrix = [
[0, 0, 2],
[2, 0, 1],
[1, 2, 3]
]
출력
True
복잡도 분석
시간 복잡도: 백트래킹 알고리즘의 특성상 최악의 경우 지수적인 시간이 소요될 수 있습니다. 각 빈 칸마다 최대 n개의 후보 값을 시도하고, 실패 시 이전 단계로 되돌아가기를 반복하기 때문입니다.
공간 복잡도: 재귀 호출 스택의 깊이는 빈 칸의 개수(최대 n²)에 비례하므로 O(n²)입니다.