문제 출처
1. 문제설명
- 스도쿠는 9x9 보드판에 숫자를 채우는 게임이다.
- 규칙은 간단하다.
- 가로 또는 세로축에 1~9의 숫자는 중복될 수 없다.
- 3x3 크기의 사각형 안에도 1~9까지의 숫자가 중복될 수 없다.
- 빈칸이 0으로 채워져있을 때 완전한 스도쿠를 구하라.
2. 알고리즘 설계
DFS
로 값을 채워나가되,
- 언급한 스도쿠 조건에 맞는지 검사하면 된다.
3. 로직
- 가로 또는 세로 방향에 같은 값이 있는지 체크하는 건 간단하니 생략
- 3x3 크기의 사각형은
(x, y)
라는 현재 좌표가 주어질 때
- 이 값을 3으로 나누고 3을 곱하면
- 몇 번째 사각형에 속하는 지 알 수 있다.
int
나눗셈의 소수점이 버려지는 걸 이용하였다.
4. 전체 코드
5. 소감
- 이 문제의 약간 헷갈릴 수 있는 부분은
- 전부 빈칸인 스도쿠가 주어질 수 있다는 것이다.
- 예제만 보고, 중간 중간 몇 개만 비워져있겠구나 생각하면 안된다!