백 트래킹. [2580]

[1. 문제 설명]

스도쿠 규칙에 맞게 9x9 배열을 채워서 출력한다.

 

 

[2. 풀이 접근]

잘못된 풀이

1차 풀이는 배열의 모든 원소에 접근 후,

해당 원소 값이 0인 경우,

1 ~ 10 까지 값 중에서 행/열, 그리고 작은 사각형 내 에서 허용된 값인 경우

해당 값을 이차원 배열에 할당 한다.

위 과정 전체를 하나의 문제로 놓고 재귀 호출한다.

 

이렇게 구현한 경우 시간초과로 인해 실패 처리되었다.

 

시간 초과에 대한 정확한 원인은 잘 모르겠지만, 아래와 같은 이유 때문으로 추정한다.

 

채워야 할 값의 위치가 아래와 같을 때

[y,x] = [ [0,0], [0,1], [3,3] ]

 

for y < 9

   for x < 9

      // [y, x] 가 0인 경우 아래를 수행

      /// 재귀 호출로 실행 된 경우, [0, 0] 은 패스 됨. 

       for c<10

           // 여기서 최초 [0,0] 에 적당한 값이 선정 됨 => 선정 기준은 코드 참조

           // 재귀 호출 수행 ~~~

           // 재귀 종료 

 

재귀 호출 된 경우, 재귀 호출 전 설정 된 값이 있기 때문에 중복 문제는 발생하지 않을 거라 생각했다.

그러나 재귀 호출 자체가 3번 중첩 된 반복문 내 에서 호출되기 때문에

내가 예측하지 못한 중복문제가 계속 발생하여 시간 초과가 발생된 것으로 여겨진다.

 

 

최종 풀이

반복문을 최대한 중첩하지 않았다.

채워야 할 위치를 배열에 저장 후

재귀 호출 시 체크 할 배열의 offset 을 갱신하는 방식으로 접근하였다.

 

 

 

[3. 코드]

 

 

 

 

[4. 시간초과 코드]