https://www.acmicpc.net/problem/2580
2580번: 스도쿠
스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루
www.acmicpc.net
백트래킹 문제다.
풀이
실제로 스도쿠를 풀듯이 각 칸에 대한 숫자 대입 여부를 확인하면 된다. 그걸 어떻게 구현하느냐가 문제의 핵심. 결국 생각이 나지 않아 다른 분의 풀이에서 힌트를 얻고 문제를 풀었다.
스도쿠 판의 각 열, 행, 사각형에 1부터 9를 대입할 수 있는 2차원 배열을 생성한다. 입력받은 스도쿠 탐색 시 0을 마주하였을 경우 앞에서 생성한 3개의 배열에 대입하려는 숫자에 해당하는 인덱스가 모두 false인 경우, 숫자를 현재 좌표에 대입 후 재귀 호출, 해당 숫자가 답이 아닐 수 있으므로 0으로 복구시킨 후 다음 탐색을 수행한다.
마지막 좌표에 도달하면 스도쿠를 출력하면 된다.
정답 코드
'Problem Solving > BOJ' 카테고리의 다른 글
| [18116] 로봇 조립 (0) | 2022.12.09 |
|---|---|
| [3190] 뱀 (0) | 2022.12.08 |
| [11559] Puyo Puyo (0) | 2022.12.05 |
| [17070] 파이프 옮기기 1 (8) | 2022.12.01 |
| [12851] 숨바꼭질 2 (0) | 2022.11.30 |