[BOJ] 2580번: 스도쿠

https://www.acmicpc.net/problem/2580

0으로 차있는 빈칸들에 대해, 우선 반드시 하나의 값으로 고정되는 경우를 먼저 처리하고 그 후 남아있는 빈칸들에 대해 백트래킹으로 1~9까지를 넣어보면서 처리를 하면 되는데, 이 때 까닥하다가 시간을 넘길까 싶어 시간을 줄이기 위한 다양한 방법을 고안했습니다. 저같은 경우에는 (i, j)칸이 0일 경우 blank[idx]에 (i, j)를 저장했고, blank[a]에 대해, blank[a]에 영향을 줄 수 있는 모든 blank[j]를 따로 저장했습니다. 또한 valid[i][j]에 (i, j)칸에 들어갈 수 있는 수의 목록을 저장했습니다.

이를 통해 백트래킹에서 특정 값을 특정 칸에 들어가도 되는지 최대한 적은 연산으로 알아낼 수 있도록 했습니다.

이게 지역본선 초등부, 중등부 문제라니 믿기지가 않습니다.

https://github.com/encrypted-def/BOJ/blob/master/2580.cpp