2239번: 스도쿠
스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다
www.acmicpc.net
DFS를 이용해 해결 가능한 문제다.
자료를 담고 있는 컨테이너의 형태가 트리, 그래프 형태가 아니더라도 깊이 우선 탐색은 사용 할 수 있다고 생각한다.
(컨테이너의 형태가 다를때, 다른 이름으로 부르는 정식 명칭이 있다면 알려주시면 감사합니다.)
아이디어는 간단하다. 좌측 상단부터 시작하여 0이 들어있는 인덱스를 찾고, 해당 인덱스에 들어갈 수 있는 숫자를 오름차순으로 넣어보며 탐색을 계속 하는 것 이다.
그렇게 모든 탐색이 끝난다면 해당 순간의 스도쿠 보드 상태가 정답이 된다.
좌측상단부터 + 낮은 숫자부터 시도하는 이유는 아래의 조건을 만족하기 위해서 이다.
답이 여러 개 있다면 그 중 사전식으로 앞서는 것을 출력한다. 즉, 81자리의 수가 제일 작은 경우를 출력한다.
깊이 우선을 떠올리는것 자체 말고는 설명할 부분이 딱히 없기 때문에 자세한 내용은 코드를 참고하면 좋을 것 같다.
code
GitHub - YoungWoo93/algorithmOnlineJudge: 알고리즘 온라인 저지
알고리즘 온라인 저지. Contribute to YoungWoo93/algorithmOnlineJudge development by creating an account on GitHub.
github.com
'알고리즘 온라인 저지 > BOJ' 카테고리의 다른 글
| BOJ 2294번 동전 2 (0) | 2022.08.10 |
|---|---|
| BOJ 7579번 앱 (0) | 2022.06.24 |
| BOJ 15711번 환상의 짝꿍 (0) | 2022.05.17 |
| BOJ 11057번 오르막 수 (0) | 2022.05.12 |
| BOJ 1389번 케빈 베이컨의 6단계 법칙 (0) | 2022.05.12 |
