반응형
스도쿠
-
BOJ) 스도쿠 (2580 번)알고리즘/백준 2021. 2. 14. 23:13
스도쿠 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 스도쿠의 조건에 따라 로직을 짜주었고, 백트래킹을 이용했다. (백트래킹을 사용하지 않으면 시간초과가 난다) 우선, 재귀 함수를 사용할 예정이어서 모든 스도쿠 맵을 돌면서 빈칸인 곳을 찾는 것이 비효율적이라고 생각했다. 그래서, 스도쿠 맵을 저장할 때, 비어있는 칸의 위치를 List에 저장해서 빈 칸들만 순회하도록 만들었다. 그리고, 빈 칸들에 들어갈 수 있는 모든 수를 넣어보면서, 적합한 수를 넣어주었다. 모든 수를 검사할 때는 빈칸의 가로와 세로에 어떤..