nano6384   6년 전

우선 맞는지 보다가 시간초과가 나면 그때 최적화를 하려고 시간은 크게 고려하지 않고 짜려했습니다.

아이디어는

1. 재귀에서 파라미터로 넘어온 배열을 보고 빈칸을 찾는다. (가장 먼저 나오는 빈칸 하나만 찾음)

2. 빈칸이 물려있는 행과 열을 보고 들어갈 수 있는 수를 추려 하나씩 넣어본다(하나 넣으면 다음 재귀 호출)

3. 각 재귀 호출 시, 즉시 파라미터로 넘어온 배열을 보고 유효한지 판단(promising 함수) (유효하지 않으면 return, 유효하면 1,2 혹은 4번 실행)

4. 3번 검사후, 1번 검사에서 빈칸이 없으면 출력하고 종료.

아이디어가 어느 지점에서 잘못됬는지 감이 잘 안오네요.. 아무리 생각해도 잘 모르겠습니다 ㅠㅜ

도와주시면 감사하겠습니다 ㅠㅜ

nano6384   6년 전

<자문자답>

해결했습니다!

중요한 것은 값을 채워 놓고 backtracking으로 돌아갔을 때, 이전 재귀에서 배열의 형태가 달라질 수 있습니다.

따라서 backtracking을 할때 빈칸에 채워놓은 값을 다시 0으로 바꿔줘야했습니다.

이를 하니 해결이 됬습니다.

nano6384   6년 전

즉, backtracking할 때는 자기가 한거는 없는게 되도록 

자신의 흔적은 싹 지워줘야하는걸 알았습니다.

gamy0315   3년 전

덕분에 빨리 알았어요 감사합니다

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