https://www.acmicpc.net/problem/2580
2580번: 스도쿠
스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루
www.acmicpc.net
백트래킹 문제다.
풀이
실제로 스도쿠를 풀듯이 각 칸에 대한 숫자 대입 여부를 확인하면 된다. 그걸 어떻게 구현하느냐가 문제의 핵심. 결국 생각이 나지 않아 다른 분의 풀이에서 힌트를 얻고 문제를 풀었다.
스도쿠 판의 각 열, 행, 사각형에 1부터 9를 대입할 수 있는 2차원 배열을 생성한다. 입력받은 스도쿠 탐색 시 0을 마주하였을 경우 앞에서 생성한 3개의 배열에 대입하려는 숫자에 해당하는 인덱스가 모두 false인 경우, 숫자를 현재 좌표에 대입 후 재귀 호출, 해당 숫자가 답이 아닐 수 있으므로 0으로 복구시킨 후 다음 탐색을 수행한다.
마지막 좌표에 도달하면 스도쿠를 출력하면 된다.
정답 코드
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import Foundation | |
| var row = Array(repeating: Array(repeating: false, count: 10), count: 10) | |
| var col = Array(repeating: Array(repeating: false, count: 10), count: 10) | |
| var rect = Array(repeating: Array(repeating: false, count: 10), count: 10) | |
| var map = Array(repeating: Array(repeating: 0, count: 9), count: 9) | |
| var flag = false | |
| for i in 0..<9{ | |
| let line = readLine()!.split(separator: " ").map{Int($0)!} | |
| for k in 0..<9{ | |
| map[i][k] = line[k] | |
| if map[i][k]>0{ | |
| let num = map[i][k] | |
| row[i][num] = true | |
| col[k][num] = true | |
| rect[(i/3)*3+(k/3)][num] = true | |
| } | |
| } | |
| } | |
| func btk(cnt:Int){ | |
| if flag{ return } | |
| let x = cnt/9 | |
| let y = cnt%9 | |
| if cnt == 81{ | |
| for numbers in map{ | |
| for number in numbers{ | |
| print(number, terminator: " ") | |
| } | |
| print() | |
| } | |
| flag = true | |
| return | |
| } | |
| if map[x][y] > 0{ | |
| btk(cnt: cnt+1) | |
| }else{ | |
| for num in 1..<10{ | |
| if !row[x][num] && !col[y][num] && !rect[(x/3)*3+(y/3)][num]{ | |
| row[x][num] = true | |
| col[y][num] = true | |
| rect[(x/3)*3+(y/3)][num] = true | |
| map[x][y] = num | |
| btk(cnt: cnt+1) | |
| map[x][y] = 0 | |
| row[x][num] = false | |
| col[y][num] = false | |
| rect[(x/3)*3+(y/3)][num] = false | |
| } | |
| } | |
| } | |
| } | |
| btk(cnt: 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 |