sukwoo0711   6년 전

제가 구현한 방법은 

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으로 돌려놔야 하는 이유를 잘 모르겠네요...


chogahui05   6년 전

사실 스토쿠를 구현하는 방법은 여러 가지가 있습니다.

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까지 넣어본 경우는 서로 별개이지요.


이게 백 트래킹의 기본 원리입니다.

h0ngjun7   6년 전

promising에서 체크할 때, 0으로 되돌려주지 않으면 그 전에 기록했던 잘못된 값이 반영되어서 영향을 미치는 것 같아요.

그러니까 예를 들면, 3번째 index 탐색이 끝나고 값이 남아있는데 (1 ~ 9 사이의 값)

다시 2번째 index에서 다음 i를 채울 때 그 전에 지우지 않았던 값이 영향을 미치는...

promising에서 a배열 뿐만 아니라, 해당 배열에 값이 들어있는지 체크하는 배열을 사용했다면 주석 처리해도 맞을 거에요.

h0ngjun7   6년 전

백트랙킹의 기본 원리라기보다는, 구현상의 문제인 것 같아요.

h0ngjun7   6년 전

질문글을 아주 상세하게 적어주셔서 답변드리기 수월했네요. 좋은 질문이에요.

sukwoo0711   6년 전

@chogahui05 님 @appa 님  먼저 답변 해주신 내용 정말로 감사합니다.


마지막으로 제가 이해한 내용이 맞는지 한번만 더 여쭈어보고싶습니다 ㅠ.ㅠ

일단 채워야 할 공간의 갯수가 3개라고 가정을 하면, 

나올 수 있는 경우의 수는 (1~9) *(1~9) *(1~9)로 총 729 개 입니다.

이걸 무식하게 다 넣어서 검사하는 방법이 브루트포스 이고,

기본적으로 모든 백트래킹 문제는 브루트포스로 해결할 수 있지만, 가짓수가 조금만 커져도 너무 오래걸립니다.

따라서, 이분탐색 처럼 절대 해가 나올 수 없는 경우를 제외한 뒤 , 검사해봐야 할 방향을 정하는게 백트래킹 이라고 이해하고 있는데,맞나요??

그리고 저 소스에서 3중 for문으로 

a[0] : 1

a[1] :1 2

a[2] : 1

a[3] : 1 2 3....9(해를 발견하지 못했음)

의 경우라고 하면, a[3]에는 9를 선 대입하고 검사를 했기때문에 a[3] = 0으로 돌려놓지 않으면, a[3] = 9의 값이 남아있잖아요?

따라서 다른 경우를 조사하기위하여 

a[0] : 1

a[1] : 1 2

a[2] : 1 2

a[3] : 1부터 다시 선 대입한 후 promising으로 가능성을 검사함. ---> 앞에서 미리 a[3]을 0으로 돌려놓을 필요가 없음

이런 생각이 들어서 질문한 내용인데, a[3]을 0으로 돌려놓는 것과 돌려놓지 않는 것이 정답에 영향을 끼칠까요??



sukwoo0711   6년 전

@appa,@chogahui05 

아 이해했습니다!!!!

값을 탐색하는데 있어서 남아있는 값이 방해가되는군요!!!!!!

원래는 0이어야되는데, 9라는 값이 잔류하고있으니까 이전 재귀로 돌아와서 탐색할 때 9를 고려하지 못하네요

감사합니다 ㅠㅠ 수정이 안되서 글 하나 더남기네요
정말 감사합니다

댓글을 작성하려면 로그인해야 합니다.