Note
9×9 스도쿠 보드에서 채워진 칸만 검사해, 행·열·3×3 서브박스 각각에 1~9가 중복 없이 들어가는지 판별하는 원리입니다.
검사 규칙
스도쿠가 유효하려면 다음 세 가지를 모두 만족해야 합니다.
- 행: 각 행에 1~9가 최대 한 번씩만 등장
- 열: 각 열에 1~9가 최대 한 번씩만 등장
- 3×3 서브박스: 9개의 3×3 영역 각각에 1~9가 최대 한 번씩만 등장
빈 칸('.')은 검사하지 않고, 채워진 숫자만 중복 여부를 확인합니다.
(유효하다고 해서 반드시 풀 수 있는 것은 아님)
아이디어: 구역별로 “이미 본 숫자” 관리
각 숫자가 어느 행·열·박스에서 이미 나왔는지 기억해 두고, 같은 구역에서 다시 나오면 invalid로 처리합니다.
- 행 i: “i번째 행에서 이미 등장한 숫자” 집합
- 열 j: “j번째 열에서 이미 등장한 숫자” 집합
- 3×3 박스: “(i,j)가 속한 박스에서 이미 등장한 숫자” 집합
집합(set)을 쓰면 “이미 봤는지”를 O(1)에 확인·추가할 수 있습니다.
3×3 박스 인덱스
보드를 3×3으로 나누면 다음과 같이 9개 박스가 있습니다.
박스 (0,0) | 박스 (0,1) | 박스 (0,2)
박스 (1,0) | 박스 (1,1) | 박스 (1,2)
박스 (2,0) | 박스 (2,1) | 박스 (2,2)
칸 (i, j) 가 속한 박스 번호는:
- 행 기준:
i // 3(0~2) - 열 기준:
j // 3(0~2)
즉, 박스 인덱스 = (i // 3, j // 3) 로 두고, 박스별로 하나의 set을 두면 됩니다.
알고리즘 흐름
- 행·열·박스용 set 준비
- 행 9개, 열 9개, 박스 3×3 = 9개 → 각각 set 하나씩
- 모든 (i, j) 순회
board[i][j]가'.'이면 무시- 숫자면:
rows[i],cols[j],boxes[i//3][j//3]중 하나라도 이미 그 숫자가 있으면 → False 반환- 없으면 세 set 모두에 해당 숫자 추가
- 끝까지 무사히 돌면 → True 반환
한 번만 순회해도 되므로 시간 O(81) = O(1) (고정 크기 보드), 공간 O(1) (고정 개수의 set)입니다.
예시: 왜 Example 2가 invalid인가
Example 2에서는 왼쪽 위 3×3 박스에 8이 두 번 나옵니다.
- (0,0)에 8
- (3,0)에 8 → 같은 열 0에서 8이 두 번이므로 열 규칙 위반이기도 함
같은 박스 안에서 8을 두 번 보는 순간 (또는 같은 행/열에서 두 번 보는 순간) boxes[i//3][j//3](또는 rows[i] / cols[j])에 이미 8이 있어서 False가 됩니다.
요약
| 항목 | 내용 |
|---|---|
| 검사 대상 | 행 9개, 열 9개, 3×3 박스 9개 |
| 자료구조 | 구역별 set (이미 본 숫자) |
| 박스 인덱스 | (i // 3, j // 3) |
| 한 번 등장한 숫자가 같은 구역에 다시 나오면 | invalid → False |
관련 문제
- LeetCode 36: Valid Sudoku - 코드 구조 설명