[Leetcode] 36. Valid Sudoku

문제 : https://leetcode.com/problems/valid-sudoku/

---

 

9 x 9 스도쿠 보드가 유효한지 확인해라. 채워진 셀만으로 다음 규칙을 만족하는지 검증해야 한다.

각 행, 열은 반복 없이 숫자 1~9를 포함해야 한다.

그리드의 3x3 하위 사각형 블럭은 반복 없이 숫자 1~9를 포함해야 한다.

---

숫자를 포함하는지 비트 연산으로 확인한다.

변수의 이름을 visits으로 하고 초기값은 0이며 i 숫자를 포함한다면 visits or (1 << i) 연산으로 visits 변수를 갱신한다. 

갱신 전에 visits and (1 << i) 결과가 0 보다 큰 경우 i 숫자를 이미 포함되었다고 본다.

 

먼저 각 행, 열을 탐색하며 위 연산으로 visits을 갱신해가며 visits 갱신 전에 i 숫자를 이미 포함한 경우 유효한 스도쿠 보드가 아니다.

 

[그림 1]

3x3 하위 사각형 블럭의 인덱스는 [그림 1]과 같다. 

i번째(0-based) 요소를 탐색한다고 할 때, 배열의 인덱스는 (s + (i/3), e + (i%3))이 된다. (참고: 배열 행 우선 순위, 열 우선 순위 )

위 방법으로 (s, e)만 고정된다면 하위 사각형 블럭의 요소들에 접근 가능하고 행, 열과 비슷한 방법으로 visits을 갱신해가며 유효한지 체크한다.

9x9 보드이므로, (s, e)를 0부터 3씩 더해가며 (0, 0), (0, 3), (0, 6), (3,0) ... (6, 6) 총 9번 반복하며 하위사각형을 체크한다.

 

시간복잡도는 O(1). 더 상세히 보면 행, 열을 탐색하는데 O(2 * 9^2). 하위 사각형 블럭을 탐색하는데 O(9^2)가 소요되므로 O(3 * 9^2).

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/36.%20Valid%20Sudoku.cpp

---

오랜만에 스도쿠하고 싶네