2580번: 스도쿠 Hint

2580번 스도쿠 문제는 전형적인 Backtracking 문제이다.

해결할 때에는 다음을 고려하자.

 

1. 조작하고, 되돌린다. 이는 Recursive 하다.

 

backtracking의 과정을 tree로 생각하면, 각 노드는 3-4-... 와 같을 것이다.

여기서 4는 (3이 넣어진 상태에서) 다른 빈칸에 넣는 것이므로,

재귀적으로 구현하되, 각 재귀 호출 전과 후에 상태를 조작하고 되돌리는 코드를 작성한다.

 

2. 시간 초과를 위해 미리 계산한다.

 

어떤 숫자를 스도쿠 빈칸에 넣었을 때 그 결정이 적절함을 어떻게 확인할 수 있을까?

1차원적인 방법으로는 빈 위치에 숫자를 넣고, 그 위치에 해당하는 가로줄, 세로줄, 박스(3X3)에서 넣은 숫자가 중복되는지 확인할 수 있다.

하지만 이는 반복문의 연속이며, 모든 경우의 모든 넣는 숫자에 대해 확인하므로 매우 비효율적이다.

대신 가로, 세로, 박스에 어떤 숫자가 비었는지 미리 저장하고, backtracking 시 이를 조작하고 복원하는 과정을 사용하면 시간을 줄일 수 있다.