LeetCode

LeetCode 36 Valid Sudoku 풀이: 행·열·박스 해시 검증

작성·코드 검증: solve together · 작성 언어: Python

0. 문제 링크와 출처

각 행과 열뿐 아니라 숫자가 속한 3×3 박스까지 동시에 중복을 검사해야 한다. 박스의 위치를 계산하고 세 종류의 방문 기록을 한 번에 관리해야 하므로 단순한 배열 순회보다 자료구조 설계가 필요해 Level 3으로 판단했다.

1. 문제 요약

9×9 스도쿠 보드가 주어질 때, 현재 채워진 숫자들이 스도쿠 규칙을 위반하지 않으면 True, 중복이 있으면 False를 반환한다.

검사해야 하는 규칙은 다음과 같다.

  • 각 행에 숫자 1부터 9가 중복 없이 등장해야 한다.
  • 각 열에 숫자 1부터 9가 중복 없이 등장해야 한다.
  • 각 3×3 박스에 숫자 1부터 9가 중복 없이 등장해야 한다.
  • .은 비어 있는 칸이므로 검사에서 제외한다.
  • 보드가 완성 가능한지 또는 실제로 풀 수 있는지는 검사하지 않는다.

즉, 빈칸이 많아도 세 규칙에 중복이 없다면 유효한 보드다. 반대로 숫자가 한 행에서 중복되지 않더라도 같은 3×3 박스 안에서 중복되면 유효하지 않다.

2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명

구간 판정

각 셀 (row, col)의 숫자를 읽을 때 다음 세 곳의 집합을 확인한다.

  • rows[row]: 현재 행에서 본 숫자
  • cols[col]: 현재 열에서 본 숫자
  • boxes[box_index]: 현재 3×3 박스에서 본 숫자

현재 값이 세 집합 중 하나에 이미 있다면 해당 규칙을 위반한 것이므로 즉시 False를 반환한다. 어느 집합에도 없다면 세 집합에 모두 추가하고 다음 칸으로 이동한다.

3×3 박스 번호는 다음 수식으로 계산한다.

box_index = (row // 3) * 3 + (col // 3)

행을 3으로 나눈 몫은 박스의 세로 그룹 0, 1, 2를, 열을 3으로 나눈 몫은 가로 그룹 0, 1, 2를 나타낸다. 여기에 * 3을 적용하면 9개 박스를 0부터 8까지 고유하게 표현할 수 있다.

한 셀에서 행·열·박스 상태를 함께 갱신하기

각 숫자는 현재 셀의 행, 열, 박스라는 세 범위에 동시에 속한다. 따라서 행·열·박스를 각각 따로 순회할 필요 없이 셀을 한 번 방문할 때 세 집합에 동시에 기록할 수 있다. 이렇게 하면 중복을 발견하는 즉시 종료할 수 있고, 세 검사의 로직도 하나의 상태 전이로 통합된다.

이 문제는 보드의 숫자를 채우는 문제가 아니다. 빈칸을 어떤 숫자로 채울 수 있는지 탐색하거나 보드의 해답을 찾을 필요 없이, 현재 채워진 값 사이의 충돌만 검사하면 된다.

상태 전이와 경계 처리

각 셀에서 다음 순서로 처리한다.

  1. 값이 .이면 건너뛴다.
  2. 현재 행, 열, 박스의 집합에 값이 이미 있는지 확인한다.
  3. 중복이면 False를 반환한다.
  4. 중복이 아니면 세 집합에 값을 추가한다.
  5. 모든 셀을 통과하면 True를 반환한다.

보드는 항상 9×9이고 셀 값도 1부터 9 또는 .으로 제한되므로 별도의 입력 범위 검사는 필요하지 않다.

시간·공간 복잡도

81개 셀을 한 번씩 방문하고 집합 조회와 삽입은 평균 O(1)이므로 시간 복잡도는 O(9 × 9), 일반적인 n × n 격자로 표현하면 O(n²)다. 행·열·박스 집합에 저장되는 숫자는 각 범위당 최대 9개이므로 공간 복잡도는 O(9 × 9), 일반화하면 O(n²)다. 이 문제의 보드 크기가 고정되어 있으므로 실제로는 상수 공간에 가깝다.

3. 문제 해결 코드 (Python)

class Solution:
    def isValidSudoku(self, board: list[list[str]]) -> bool:
        rows = [set() for _ in range(9)]
        cols = [set() for _ in range(9)]
        boxes = [set() for _ in range(9)]

        for row in range(9):
            for col in range(9):
                value = board[row][col]

                if value == ".":
                    continue

                box_index = (row // 3) * 3 + (col // 3)

                if (
                    value in rows[row]
                    or value in cols[col]
                    or value in boxes[box_index]
                ):
                    return False

                rows[row].add(value)
                cols[col].add(value)
                boxes[box_index].add(value)

        return True

rows, cols, boxes는 각각 9개의 집합을 가지며, 같은 숫자가 행·열·박스 중 하나에서 두 번째로 발견되면 즉시 종료한다. 숫자를 세 집합에 모두 추가해야 이후 셀에서 세 규칙을 동시에 검사할 수 있다.

4. 오답 접근과 반례

행과 열만 검사하기

행과 열에 중복이 없더라도 같은 3×3 박스에 중복이 있을 수 있다. 공식 두 번째 예제는 첫 번째 행의 5를 8로 바꾼 보드인데, 행과 열 일부만 확인하면 놓치기 쉽고 왼쪽 위 3×3 박스에 8이 두 개 생기므로 유효하지 않다.

왼쪽 위 박스:
8 3 .
6 . .
. 9 8

박스별 집합을 별도로 유지해야 이 충돌을 발견할 수 있다.

박스 번호를 덧셈으로만 계산하기

다음 식은 박스를 고유하게 구분하지 못한다.

box_index = row // 3 + col // 3  # 잘못된 계산

예를 들어 박스 그룹 (0, 1)과 (1, 0)이 모두 1이 되어 서로 다른 박스의 숫자를 같은 집합에서 검사하게 된다. 세로 그룹과 가로 그룹을 조합하려면 다음처럼 * 3을 적용해야 한다.

box_index = (row // 3) * 3 + col // 3

빈칸을 숫자로 처리하기

.은 비어 있는 칸을 의미하므로 집합에 넣으면 안 된다. 모든 행에 .이 여러 개 있는 것은 정상이며, 이를 중복으로 판단하면 유효한 보드도 False가 된다.

유효성 검사와 풀이 가능성 혼동하기

현재 보드에 중복이 없다면 유효한 보드다. 이후 빈칸을 실제로 채울 수 있는지까지 확인하는 것은 별도의 스도쿠 풀이 문제이며, 이 문제에서는 백트래킹이나 완전탐색을 수행할 필요가 없다.

복사해 실행할 테스트

아래 assert를 풀이 코드와 같은 Python 파일에 붙여 실행하면 빈 보드와 행 중복 경계를 확인할 수 있다.

solver = Solution()
empty_board = [["."] * 9 for _ in range(9)]
assert solver.isValidSudoku(empty_board) is True

duplicate_row = [row[:] for row in empty_board]
duplicate_row[0][0] = "5"
duplicate_row[0][1] = "5"
assert solver.isValidSudoku(duplicate_row) is False

5. 공식 예제와 추가 검증

작성한 isValidSudoku 함수를 Python으로 실행해 공식 예제와 각 규칙의 반례를 확인했다.

공식 예제

입력 기대 출력 확인 결과
첫 번째 공식 보드 True 통과
첫 번째 행의 5를 8로 바꾼 보드 False 통과

추가 검증 1: 완전히 빈 보드

입력: 모든 칸이 "."인 9×9 보드
기대 출력: True
확인 결과: 통과
검증 목적: 빈칸을 건너뛰고 중복이 없는 상태를 허용하는지 확인

추가 검증 2: 같은 행에서 중복

입력: 첫 번째 행이 ["5","3","5",".","7",".",".",".","."]인 보드
기대 출력: False
확인 결과: 통과
검증 목적: 같은 행의 숫자 중복을 즉시 검출하는지 확인

추가 검증 3: 같은 열에서 중복

입력: 첫 번째 열의 첫 두 칸이 모두 "5"인 보드
기대 출력: False
확인 결과: 통과
검증 목적: 서로 다른 행에 있어도 같은 열의 중복을 검출하는지 확인

추가 검증 4: 행·열은 다르지만 같은 박스에서 중복

입력: 왼쪽 위 3×3 박스의 (0,0)과 (1,1)이 모두 "5"인 보드
기대 출력: False
확인 결과: 통과
검증 목적: 3×3 박스 단위의 중복 검사를 확인

6. 다른 풀이 방식 검색 및 비교

행·열·박스를 각각 별도로 순회하는 세 번의 검사도 O(n²) 시간에 동작하고 구현할 수 있다. 이 글의 한 번 순회 방식은 각 셀의 숫자를 세 범위에 동시에 기록하므로 중복 검사 위치가 한 곳에 모이고, 충돌을 발견하면 즉시 반환할 수 있다.

비트마스크를 사용하면 각 행·열·박스의 숫자 집합을 정수 하나로 표현할 수도 있다. 숫자가 1부터 9까지로 고정되어 있어 효율적이지만, 이 글에서는 집합 연산이 코드의 의미를 더 직접적으로 보여주므로 해시 집합 방식을 선택했다.

마무리

Valid Sudoku는 스도쿠를 실제로 완성하는 문제가 아니라 현재 숫자 배치의 충돌만 확인하는 문제다. 각 셀을 한 번 순회하면서 행, 열, 3×3 박스의 집합에 같은 값을 기록하면 세 규칙을 동시에 검사할 수 있다. 특히 (row // 3) * 3 + col // 3으로 박스를 정확히 구분하는 것이 핵심이다.

#해시#LeetCode#난이도 3