스도쿠 채점 프로그램
스도쿠는 일본어로 "수독(數獨)"을 읽은 것이며, 9x9 격자판에서 다음 조건을 만족하도록 숫자를 채워 넣는 게임입니다:
- 각 정수 1-9는 각 행에 정확히 한 번씩 등장해야 합니다.
- 각 정수 1-9는 각 열에 정확히 한 번씩 등장해야 합니다.
- 각 정수 1-9는 각 작은 3x3 정사각형에 정확히 한 번씩 등장해야 합니다.
남규는 스도쿠를 풀었지만, 그것이 올바른 정답인지 확인하는 데 어려움을 겪고 있습니다. 이에 따라 완성된 스도쿠 판이 정답인지 확인하는 프로그램을 작성해야 합니다.
입력
입력의 첫 줄에는 테스트 케이스의 개수가 주어집니다.
각 테스트 케이스는 9개의 줄로 이루어져 있으며, 각 줄에는 9개의 정수가 공백으로 구분되어 있습니다. 각 정수는 1 이상 9 이하입니다.
테스트 케이스 사이에는 빈 줄이 하나 포함됩니다.
테스트 케이스의 개수는 100개를 넘지 않습니다.
출력
각 테스트 케이스에 대해 "Case x:"를 출력한 후, 공백 한 칸 뒤에 풀이가 올바르면 "CORRECT"를, 아니면 "INCORRECT"를 출력합니다. 여기서 x는 테스트 케이스 번호이며, 1부터 시작합니다.
예제 입력과 출력
예제 입력
2
1 2 3 5 6 7 4 8 9
3 4 5 6 1 2 4 7 8
7 5 8 3 4 2 1 9 6
1 2 3 5 6 7 4 8 9
3 4 5 6 1 2 4 7 8
7 5 8 3 4 2 1 9 6
1 2 3 5 6 7 4 8 9
3 4 5 6 1 2 4 7 8
7 5 8 3 4 2 1 9 6
3 5 7 9 6 4 2 8 1
4 6 8 1 2 3 5 7 9
9 1 2 5 8 7 4 6 3
6 3 1 7 9 5 8 4 2
7 2 4 3 1 8 6 9 5
8 9 5 2 4 6 1 3 7
1 7 6 4 5 9 3 2 8
5 8 3 6 7 2 9 1 4
2 4 9 8 3 1 7 5 6
예제 출력
Case 1: INCORRECT
Case 2: CORRECT
문제를 해결하기 위해서는 각 행 각 열 각3×3에 같은 숫자가 있는지 살펴야 합니다.
가장 나이브하게는 행검사 1번 열검사1변 3×3검사(2중 for 1번) 해도 충분히 가능해 보인다.
하지만 이중 for로 1차원 배열을 탐색하면서 1번에 검사할 수 있을 것 같았다.
이렇게 해야 세 가지 조건을 빠르게 검사하면서 하나라도 걸리면 INCORRECT를 빠르게 뱉고 다음 케이스로 넘어갈 수 있다고 생각했다. 그래서 행 검사를 순회하면서 해당 열과 행에 따라 검사용 집합 리스트에 보내고 중복 신호가 오면 멈추게 만들었다.
n,*r=map(int,open(0).read().split())
for i in range(n):
box=[set() for _ in range(9)]
col=[set() for _ in range(9)]
for j in range(9):
row=set()
for k in range(9):
curr=r[i*81+j*9+k]
if curr in row or curr in col[k] or curr in box[(idx:=(k//3)+((j//3)*3))]:break
col[k].add(curr)
row.add(curr)
box[idx].add(curr)
else:continue
print(f"Case {i+1}: INCORRECT")
break
else:
print(f"Case {i+1}: CORRECT")아래는 위 설명을 기반으로 블로그에 게시하기 위한 HTML 형식의 콘텐츠입니다. ```html
스도쿠 정답 유효성 검사 코드
주어진 입력을 받아 스도쿠 퍼즐의 정답 유효성을 검사하는 프로그램입니다. 코드를 단계별로 살펴보겠습니다.
코드 설명
1. 입력 처리
n, *r = map(int, open(0).read().split())- open(0).read(): 표준 입력에서 데이터를 읽어옵니다.
- split(): 공백 또는 줄바꿈으로 데이터를 나눕니다.
- map(int, ...): 데이터를 정수로 변환.
- 첫 번째 값 n: 테스트 케이스 개수.
- 나머지 값은 r 리스트에 저장됩니다. 이는 스도쿠 숫자들을 평면적으로 나열한 상태입니다.
2. 테스트 케이스 반복
for i in range(n):
box = [set() for _ in range(9)]
col = [set() for _ in range(9)]
- box: 각 3x3 박스별 숫자 저장.
- col: 각 열별 숫자 저장.
3. 스도쿠 행 검사
for j in range(9):
row = set()
for k in range(9):
curr = r[i * 81 + j * 9 + k]
- row: 현재 행의 숫자를 저장하는 집합.
- curr: 현재 위치의 숫자. 계산식은 평면 리스트에서 올바른 값을 가져옵니다.
4. 유효성 검사
if curr in row or curr in col[k] or curr in box[(idx := (k // 3) + ((j // 3) * 3))]:
break
- row, col[k], box[idx]에 중복된 숫자가 있으면 유효하지 않은 스도쿠로 판정. - idx: 현재 숫자가 속한 3x3 박스의 번호.
5. 숫자 추가
col[k].add(curr)
row.add(curr)
box[idx].add(curr)
유효성 검사를 통과한 숫자를 각 집합에 추가합니다.
6. 결과 출력
else:
continue
print(f"Case {i+1}: INCORRECT")
break
else:
print(f"Case {i+1}: CORRECT")
- 유효성 검사 실패 시 INCORRECT 출력.
- 모든 조건을 만족하면 CORRECT 출력.