Yunsu's Log

LeetCode 36: Valid Sudoku

8 min read

Note

행·열·3×3 박스마다 set으로 중복을 검사하는 코드 구조를 설명합니다.

문제 링크

문제 요약

  • 입력: 9×9 스도쿠 보드 (board[i][j]는 '1'~'9' 또는 '.')
  • 출력: 채워진 칸만 봤을 때 유효하면 true, 아니면 false
  • 유효 조건: 각 행, 각 열, 각 3×3 서브박스에 1~9가 중복 없이 등장

전체 코드

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        cols = [set() for _ in range(9)]
        rows = [set() for _ in range(9)]
        boxes = [[set() for _ in range(3)] for _ in range(3)]
        for i in range(9):
            for j in range(9):
                n = board[i][j]
                if n.isnumeric():
                    if n in rows[i] or n in cols[j] or n in boxes[i // 3][j // 3]:
                        return False
                    rows[i].add(n)
                    cols[j].add(n)
                    boxes[i // 3][j // 3].add(n)
        return True

코드 구조 설명

1. 행·열·박스 set 초기화

cols = [set() for _ in range(9)]
rows = [set() for _ in range(9)]
boxes = [[set() for _ in range(3)] for _ in range(3)]
  • rows[i]: i번째 행에서 이미 등장한 숫자
  • cols[j]: j번째 열에서 이미 등장한 숫자
  • boxes[r][c]: 박스 (r, c) 에서 이미 등장한 숫자 (r, c = 0~2)

2. 보드 한 번 순회

for i in range(9):
    for j in range(9):
        n = board[i][j]
  • 모든 칸 (i, j)를 한 번씩만 방문합니다.

3. 숫자 칸만 검사

if n.isnumeric():
  • '.'는 건너뛰고, '1'~'9'인 칸만 검사합니다.

4. 중복 여부 확인

if n in rows[i] or n in cols[j] or n in boxes[i // 3][j // 3]:
    return False
  • 같은 행에 이미 n이 있으면 → rows[i]
  • 같은 열에 이미 n이 있으면 → cols[j]
  • 같은 3×3 박스에 이미 n이 있으면 → boxes[i // 3][j // 3]

하나라도 참이면 유효하지 않으므로 즉시 False 반환합니다.

5. set에 추가

rows[i].add(n)
cols[j].add(n)
boxes[i // 3][j // 3].add(n)
  • 중복이 없으면, 해당 행·열·박스 set에 n을 넣어 “이미 봤다”고 표시합니다.

6. 정상 종료

return True
  • 모든 칸을 검사했는데 한 번도 False를 반환하지 않았다면 유효한 보드이므로 True 반환합 니다.

3×3 박스 인덱스

(i, j) 범위i // 3j // 3
(02, 02)00
(02, 35)01
(02, 68)02
(35, 02)10
………

boxes[i // 3][j // 3] 하나로 (i, j)가 속한 3×3 박스를 지정할 수 있습니다.

데이터 흐름 요약

단계역할
rows, cols, boxes구역별 “이미 본 숫자” set
(i, j) 순회각 칸을 한 번씩 검사
n.isnumeric()빈 칸 제외, 숫자만 검사
n in rows/cols/boxes같은 구역에서 중복이면 False
add(n)중복 없으면 세 set에 등록

시간·공간 복잡도

  • 시간: O(9²) = O(1) — 81칸, 칸마다 set 조회·추가 O(1)
  • 공간: O(1) — 행 9개, 열 9개, 박스 9개 set (고정 크기)

심화 이론

Note

9×9 스도쿠 보드에서 채워진 칸만 검사해, 행·열·3×3 서브박스 각각에 1~9가 중복 없이 들어가는지 판별하는 원리입니다.

검사 규칙

스도쿠가 유효하려면 다음 세 가지를 모두 만족해야 합니다.

  1. 행: 각 행에 1~9가 최대 한 번씩만 등장
  2. 열: 각 열에 1~9가 최대 한 번씩만 등장
  3. 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을 두면 됩니다.

알고리즘 흐름

  1. 행·열·박스용 set 준비
    • 행 9개, 열 9개, 박스 3×3 = 9개 → 각각 set 하나씩
  2. 모든 (i, j) 순회
    • board[i][j]가 '.'이면 무시
    • 숫자면:
      • rows[i], cols[j], boxes[i//3][j//3] 중 하나라도 이미 그 숫자가 있으면 → False 반환
      • 없으면 세 set 모두에 해당 숫자 추가
  3. 끝까지 무사히 돌면 → 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

그래프 뷰