사실 스토쿠를 구현하는 방법은 여러 가지가 있습니다.
COCI에서도, 나온 적이 있는 거 같네요.
promissing은 검사 함수인가요? 그리고 dfs는 스토쿠에 숫자를 넣어보는 함수입니다.
음. 넣어야 할 자리가 (1), (2), ..., (30)이라고 해 봅시다.
지금 저는 (29)번째 자리를 검사하고 있고요.
1번부터 28번째 자리까지 채웠습니다. 어떤 특정한 숫자로 채웠겠지요?
그리고 29번째 자리에 1번부터 9번까지 채워 보았습니다. 그런데 해가 없습니다.
해가 없는 경우는 promissing 함수를 호출했을 때 완벽하게 맞아 떨어지는 게 없는 경우겠지요.
그 경우에는. 28번째 자리에 다른 숫자를 집어 넣어 봐야지요. 29번째 자리는요?
28번째 자리에 다른 수를 집어 넣는다면 29번째 공간은요?
당연히 다시 탐색해야 할 겁니다. 예를 들어서
12121..1213 이렇게 넣었습니다.
그리고 29번째에 1부터 9까지 넣어봤는데 안 되었습니다.
그러면 28번째 공간에 4를 넣어봐야 하지 않을까요?
12121..1214 이렇게요.
12121..1213인 상태에서 1부터 9까지 넣어본 경우와
12121..1214인 상태에서 1부터 9까지 넣어본 경우는 서로 별개이지요.
이게 백 트래킹의 기본 원리입니다.
sukwoo0711 6년 전 1
제가 구현한 방법은
1. 최초 입력받은 0의 위치값을 벡터에 삽입
2. dfs(벡터의 인덱스) 를 통하여 벡터의 길이 == 파라미터 가 될때까지 진행
3. 0의 위치정보를 받아 1~9까지의 숫자를 집어넣어보고 조건을 검사.
4. 끝까지 진행됐다면 출력후 종료
저 소스 73번 line에
for (int i = 1; i <= 9 && onetime; i++)
{
a[px][py] = i; //일단 숫자를 넣어보고
if (promissing(px, py)) //검사 후 통과하면
{
dfs(index + 1); //다음 0의 위치를 찾아 또 검사.
}
a[px][py] = 0; //숫자 넣은걸 되돌림.
}
숫자 넣은걸 다시 되돌리는 이유는 뭐에요?
0의 좌표는 이미 받아놨으니까 a[px][py]는 어차피 덮어씌워지지 않나요??
0으로 돌려놔야 하는 이유를 잘 모르겠네요...