[SWEA] 2891. 분수 스도쿠 - DFS & 가지치기

이 글은 SW Expert Academy에 있는 문제를 풀고 정리한 글입니다.

https://swexpertacademy.com/main/code/problem/problemDetail.do

이 문제를 보고 먼저 든 생각은,

임의의 빈칸에 대해 넣을 수 있는 숫자의 목록을 반환하는 함수를 만들어야겠다

였습니다.

그러기 위해서 그 칸이 포함된 행, 열, 3x2 격자칸을 확인해보고,

분수 칸이라면 다른 쪽(분모라면 분자, 분자라면 분모)에 있는 숫자를 확인해서

1~9 중의 수에서 넣을 수 있는 수를 반환합니다.

그래서 각 빈칸마다 넣을 수 있는 수의 목록을 반환 받아서

하나씩 넣어보면서 막힌다면 다시 되돌아와서 다른 수를 넣어보는 식으로 하면 되겠죠.

그런데 이 문제의 제한 시간은 1초입니다.

만약 이 문제를 왼쪽 윗칸부터 빈칸인지 확인하면서 먼저 발견되는 빈칸을 기준으로

하나씩 수를 넣어보는 식으로 한다면, 그리고 만약 1개의 수가 아닌 여러개의 수를 넣을 수 있는 상황이라면

여러 경우를 실험해보느라 실행시간이 늘어나겠죠.

그래서 저는 수를 넣어볼 칸을 찾을때, 넣을 수 있는 숫자의 목록이 가장 짧은 칸을 먼저 찾기로 했습니다.

그를 위해서 6x6의 모든 칸에 대해 넣을 수 있는 숫자의 목록을 반환 받고,

만약 하나의 수만 넣을 수 있다면 바로 그 칸에 대해 실험해보는 것으로 알고리즘을 설계했습니다.

나름의 가지치기를 적용해서 시간 복잡도를 계산하기는 좀 어렵군요...

가지치기를 적용하지 않았다면 제 생각에는 지수 함수의 형태로 증가할 거라고 생각했지만

가지치기를 적용하지 않은 분들의 풀이가 시간안에 pass되는 것을 보면 꼭 그렇진 않은 것 같군요 ㅎㅎ

제 코드입니다. 감사합니다

http://colorscripter.com/s/U0myTan

p.s)

발견한 칸이 분수 칸일때에 대한 경우가 너무 복잡하게 설계 된것 같아 아쉽습니다.

findMin()의 반환을 행과 열의 위치와, 분모인지, 분자인지에 대한 정보를 같이 반환했다면

코드가 훨씬 깔끔했을텐데...ㅠㅠ

다음에는 함수 반환형을 좀더 잘 설계해봐야겠습니다.