15번 줄의 exit(0);이 핵심입니다.

이 문구에 의해 단 하나의 답이라도 찾으면 재귀고 뭐고 다 무시하고 "프로그램을 즉시 종료" 합니다. exit(0); 부분을 지우고 실행해보시면 가능한 모든 답을 다 출력할 겁니다.

지금 다시 보니 코드가 답이 반드시 존재하는 경우에만 올바르게 출력하고, 그렇지 않은 경우에는 제대로 동작하지 않겠네요. (반례의 예시는, 어떤 칸에 1부터 9까지의 수 중 무엇도 들어갈 수 없도록 설계한 뒤 그 자리를 0으로 만들어보세요)

문제 조건에서 반드시 답이 있는 입력만 주어진다고 했으니 이 문제는 맞겠지만 일반적으로 나아가서 답이 없는 경우의 예외처리를 요구하는 상황까지 가면 이런 로직으로는 올바른 답을 내기 어려울 겁니다.

밤에 시간 나면 이런 문제를 해결하기 위한 dfs의 통상적인 구조와 return이 어떤 방식으로 동작하는지를 예시를 들어서 작성해보겠습니다.

우선, 귀한 시간 써서 답변 주셔서 너무 감사드립니다. 

그런데 이 문제를 통상적인 dfs구조로  해결할 수 있나요?

이문제에 한해서는, 

이렇게 생각했는데 맞을까요? 

https://stackoverflow.com/ques...

제가 용어를 조금 혼용해서 사용했는데, 백트래킹을 사용한다고 표현하는 게 좀 더 알맞을 것 같네요.

아무튼, 백트래킹의 과정을 살펴보면 아래에 첨부한 pseudo-code와 같습니다.

이제 다음과 같은 4x4 미니 스도쿠를 살펴봅시다.

A C 1 B

0 0 3 4

0 0 0 0

0 0 0 0

B 자리에 반드시 2가 들어가야 하므로 A 자리에는 실제로 들어갈 수 있는 수는 3 또는 4입니다.

하지만, 단순하게 왼쪽 위부터 채우는 백트래킹 과정을 생각하면 2, 3, 4 모두 A 자리에 들어갈 수 있는 후보이며 작은 수부터 넣어보도록 구현했다면 2를 제일 먼저 시도할 겁니다.

이제 backtrack()이 호출되고, 다음 C 자리에 넣을 수 있는 후보인 3과 4중 3을 먼저 시도해보기로 합니다.

그 다음으로 또 backtrack()이 호출되고, B에 넣을 수 있는 수가 있는지 확인해보아야 할 것입니다. (1행 3열의 "1"을 건너뛰고 B로 가는 것은 구현 과정에서 고민해보아야 할 문제입니다)

이제 아래 코드의 14번 줄의 for문에서, 넣을 수 있는 수가 아무 것도 없네요. 자연스럽게 20번 줄의 return 문이 실행됩니다.

C에 넣을 수 있는 후보 숫자 중 3이 안되는 것을 확인했고, 다음 후보인 4로 넘어갑니다.

backtrack()이 호출되고, B에 넣을 수 있는 수가 있는지 확인해보지만 이번에도 역시 없습니다. 다시 20번 줄의 return 문이 실행됩니다. 이 말인즉슨, A에 2를 넣은 시점에서 C에 넣어볼 수 있는 수는 다 넣어봤다는 뜻이죠.

이제 A에 3을 넣어보게 되고, 수많은 backtrack 호출이 이어지다가 여러 답 중 하나인

3 4 1 2

1 2 3 4

2 3 4 1

4 1 2 3

을 맨 처음으로 찾게 되는 시점에 7번 줄의 if문이 참이 되어 답안을 출력하게 됩니다.

질문에서 작성하셨던 코드는 이 시점에서 exit을 호출하여 프로그램 실행을 완전히 종료하였고요, 만약 종료하지 않고 그냥 return을 했다면, 이제 가능한 다음 답안을 찾을 때까지 return과 backtrack의 호출을 계속 반복하겠지요. 모든 답안을 다 찾을 때까지요.

최종적으로 A에 3을 넣었을 때 가능한 상태를 다 시험해보고 (중간 중간에 답안을 찾을 때마다 출력할 거고요), A에 4를 넣었을 때 가능한 상태를 다 시험하고 나서 (마찬가지로 답안을 찾을 때마다 출력하겠죠) 마지막 return을 만나면 backtrack이 완전히 종료하게 될 겁니다.

한 줄 답변입니다.

Q. 얘는 return을 언제 할까?

A. 1) 답안을 찾았을 때 12번 줄에서 return, 2) 현재 상태에서 가능한 건 다 시도해봤을 때 20번 줄에서 return 합니다.