Valid Sudoku
9 × 9 스도쿠 보드를 board로 받습니다. 이는 각각 9개의 문자로 이루어진 문자열 9개로 구성된 목록이며, 각 문자열은 한 행을 나타냅니다. 각 문자는 1부터 9까지의 숫자이거나 빈 칸을 나타내는 .입니다. 한 행, 한 열 또는 3 × 3 박스에서 같은 숫자가 두 번 나타나지 않으면 true를 반환하고, 그렇지 않으면 false를 반환하세요. 채워진 칸만 확인합니다. 보드가 풀 수 있어야 하는 것은 아닙니다.
함수
- boardstring-array
- 9개의 문자로 이루어진 문자열 9개, 각 행에 하나씩, 숫자 1~9와 빈 칸을 나타내는 .
- 반환값boolean
- 행, 열 또는 3 × 3 상자에 숫자가 반복되지 않으면 true, 그렇지 않으면 false
제약 조건
board.length == 9그리고board[i].length == 9board[i][j]는1부터9까지의 숫자이거나.입니다.- 보드를 완성하는 것이 불가능할 수도 있습니다. 채워진 셀들 사이의 반복만 중요합니다.
예제
- 입력
- board = [".19......", "..89...3.", ".3.8.....", ".5..6....", ".74..89.3", "....7....", ".2.5..19.", "1....3...", ".8......7"]
- 출력
- true
- 설명
- 0부터 세었을 때 4번째 행인
.74..89.3에는 7, 4, 8, 9, 3이 각각 한 번씩 있으며, 나머지 26개 그룹 중 어느 것도 숫자를 반복하지 않습니다.
- 입력
- board = ["3.64.....", "258..9..1", "...8.2...", "...9...43", ".6.1..28.", "....87.65", "8......24", "3.......6", "6....45.8"]
- 출력
- false
- 설명
- 0행과 7행은 모두
3으로 시작하므로 0열에는 3이 두 개 있습니다. 두 숫자는 같은 행이나 박스에 있지 않으므로 열 검사만으로 이를 잡아낼 수 있습니다.
- 입력
- board = ["987..36.5", "2.6.8..13", ".1.64.75.", "8..261..4", "16.97.3.8", "..9.5..6.", "7.....49.", "..48.....", "5.1.....7"]
- 출력
- false
- 설명
- 0행 8열의
5와 2행 7열의5는 같은 행이나 열에 있지 않지만, 둘 다 오른쪽 위 상자에 있으므로 답은false입니다.
후속 질문
4 × 4 상자와 1부터 9까지 및 A부터 G까지의 기호가 있는 16 × 16 보드는 어떻게 확인하나요? 상자 공식은 어떻게 바뀌나요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
규칙에서 다루는 그룹들을 나열하세요. 그룹은 몇 개이며, 색인을 만들기 가장 어려운 종류는 무엇인가요?
r행c열에 있는 셀은 정확히 하나의 박스에 속합니다. 정수 나눗셈을 사용하면r / 3은 셀이 어느 3행 묶음에 있는지,c / 3은 어느 3열 묶음에 있는지 나타냅니다. 두 값을 결합해 0부터 8까지의 숫자 하나로 만듭니다.각 칸을 한 번씩 방문하세요. 모든 (행, 숫자), (열, 숫자), (박스, 숫자) 쌍마다 방문 여부 플래그를 유지하세요. 세 그룹 중 어느 하나에서든 플래그가 이미 설정된 채워진 칸은 중복입니다.
풀이
각 숫자는 세 그룹, 즉 해당 행, 열, 3 × 3 박스에 속합니다. 행과 열은 인덱싱하기 쉽지만, 버그는 박스에서 발생합니다. (r / 3) * 3 + c / 3을 사용해 박스에 0부터 8까지 번호를 매기면, 81개 셀을 한 번 순회하면서 27개 그룹을 모두 확인할 수 있습니다.
각 행, 열, 박스를 각각 확인하세요
핵심 아이디어
규칙은 27개의 그룹을 지정합니다. 9개의 행, 9개의 열, 9개의 박스입니다. 각 그룹의 아홉 셀을 모아 점은 무시하고 반복되는 숫자가 있는지 확인합니다. 어느 그룹에도 반복되는 숫자가 없을 때만 보드가 유효합니다.
숫자마다 확인 플래그를 두면 아홉 셀에서 반복을 찾을 수 있습니다. 81개의 셀을 각 셀이 속한 세 그룹에서 한 번씩 읽으므로, 총 243번 읽으며 작업량은 고정되어 있습니다. n × n 보드에서는 같은 방법의 비용이 O(n²)입니다.
알고리즘
i가 0부터 8까지일 때, 행i, 열i, 박스i를 수집합니다.- 박스
i의 모서리는 행3 * (i / 3), 열3 * (i % 3)에 있습니다. 박스의 셀k는 모서리에서 아래로k / 3행, 오른쪽으로k % 3열 떨어져 있습니다. - 각 그룹을 새로운 방문 여부 플래그와 함께 순회하며, 점은 건너뜁니다. 숫자가 이미 표시된 경우
false를 반환합니다. - 27개 그룹을 모두 확인한 후
true를 반환합니다.
def has_repeat(cells):
seen = set()
for ch in cells:
if ch == '.':
continue
if ch in seen:
return True
seen.add(ch)
return False
def isValidSudoku(board):
for r in range(9):
if has_repeat(board[r][c] for c in range(9)):
return False
for c in range(9):
if has_repeat(board[r][c] for r in range(9)):
return False
for top in (0, 3, 6):
for left in (0, 3, 6):
box = (board[top + i][left + j] for i in range(3) for j in range(3))
if has_repeat(box):
return False
return True행, 열, 박스마다 확인한 항목을 기록하는 테이블을 사용하는 한 번의 순회
핵심 아이디어
각 셀을 한 번씩 방문하면서 세 가지 질문을 모두 함께 확인하세요. 플래그 테이블 세 개(각각 9 × 9)를 유지하세요. seenRow[r][d]는 숫자 d+1이 이미 행 r에 있음을 나타내고, seenCol과 seenBox도 같은 방식으로 작동합니다.
셀 (r, c)은 박스 (r / 3) * 3 + c / 3에 속합니다. 첫 번째 부분은 세 박스로 이루어진 띠를 선택하고, c / 3은 그 띠 안의 박스를 선택합니다. 셀 (4, 7)은 박스 1 * 3 + 2 = 5, 즉 가운데 오른쪽 박스에 속합니다.
이미 설정된 플래그는 해당 그룹에서 숫자가 반복된다는 뜻입니다. 각 셀은 한 번씩 읽고 테이블에는 243개의 플래그가 저장됩니다. 여기서 시간과 메모리는 고정이며, n × n 보드에서는 O(n²)입니다.
알고리즘
seenRow,seenCol,seenBox를 각각 9 × 9 크기로 만들고 모두 false로 설정합니다.- 채워진 모든 셀
(r, c)에 대해,d를 해당 숫자에서 1을 뺀 값으로 두고b = (r / 3) * 3 + c / 3로 설정합니다. seenRow[r][d],seenCol[c][d]또는seenBox[b][d]가 설정되어 있으면false를 반환하고, 그렇지 않으면 세 항목을 모두 설정합니다.- 마지막 셀을 확인한 후
true를 반환합니다.
def isValidSudoku(board):
# seen_row[r][d] is True once digit d + 1 appears in row r; same for columns and boxes.
seen_row = [[False] * 9 for _ in range(9)]
seen_col = [[False] * 9 for _ in range(9)]
seen_box = [[False] * 9 for _ in range(9)]
for r in range(9):
for c in range(9):
ch = board[r][c]
if ch == '.':
continue
d = int(ch) - 1
b = (r // 3) * 3 + c // 3
if seen_row[r][d] or seen_col[c][d] or seen_box[b][d]:
return False
seen_row[r][d] = seen_col[c][d] = seen_box[b][d] = True
return True
함정과 경계 사례
r / 3 + c / 3로 상자를 계산하는 경우. 결과는 0부터 4까지만 나오므로, 상자가 다른(0, 3)과(3, 0)이 같은 숫자를 공유하고, 그곳에 7이 두 개 있으면 중복으로 보고됩니다./로 나누는 경우. JavaScript, Python 3 또는 Lua에서는4 / 3이1.33입니다. 내림하세요..을 값으로 취급하는 경우. 빈 보드에는 각 행에 점이 9개 있으므로 유효합니다.- 퍼즐을 풀려고 하는 경우. 행 0이
12345678.이고 열 8의 아래쪽에 9가 있으면 절대 완성할 수 없지만, 중복되는 것은 없습니다.true. - 상자를 건너뛰는 경우. 각 행이 바로 위 행을 왼쪽으로 한 칸씩 이동한 완성된 격자에서는 어떤 행이나 열에도 중복이 없지만, 모든 상자에는 중복이 있습니다.
자주 묻는 질문3
Valid Sudoku의 시간 복잡도는 얼마인가요?
보드에는 항상 81개의 셀이 있으므로 두 접근 방식 모두 O(1) 시간에 실행되고 O(1) 메모리를 사용합니다. 일반적인 n × n 스도쿠의 경우 한 번의 검사로 n²개의 셀을 각각 한 번씩 읽고 3n²개의 플래그를 유지하므로 시간과 메모리는 O(n²)입니다.
유효한 스도쿠 보드는 반드시 풀 수 있어야 하나요?
아니요. 여기서 유효하다는 것은 채워진 칸들 가운데 같은 행, 같은 열 또는 3 × 3 박스에 같은 숫자가 반복되지 않는다는 뜻일 뿐입니다. 보드는 이 검사를 통과하더라도 여전히 해답이 없을 수 있습니다. 해답이 있는지 판단하려면 백트래킹과 같은 탐색이 필요하며, 이는 별개의 문제입니다.
비트 마스크로 유효한 스도쿠를 풀 수 있을까요?
네. 각 행, 열, 박스에 정수 하나씩 할당합니다. 비트 d는 숫자 d+1이 이미 나왔음을 뜻합니다. 채워진 셀의 경우, 1 << d를 세 마스크 중 어느 하나와 AND 연산했을 때 결과가 0이 아니면 숫자가 반복된 것이고, 그렇지 않으면 세 마스크 모두에 OR 연산으로 추가합니다. 이렇게 하면 플래그 243개 대신 정수 27개를 사용합니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
def isValidSudoku(board):
# 여기에 코드를 작성하세요테스트 #1
테스트 #2
테스트 #3
인자
board = [".19......", "..89...3.", ".3.8.....", ".5..6....", ".74..89.3", "....7....", ".2.5..19.", "1....3...", ".8......7"]
예상 출력
true