[2239] 스도쿠

이 문제는 처음봤을 때 복잡해 보였지만 풀어보니 빈칸에 들어올 수 있는 숫자를 구하는 부분과 DFS 함수만 구현하면 쉽게 풀 수 있는 문제인 것을 느꼈다.

 

 

먼저 빈칸에 들어갈 수 있는 수를 확인하는 함수이다. 칸 index와 확인하고자 하는 숫자를 받아서 해당 칸의 가로세로로 동일한 숫자가 있는지 먼저 계산한다. 처음에는 가로 세로니까 이중 for문으로 구현했는데 단일 for문으로도 구현이 가능했다.가로 세로 모두 0부터 8 index의 값을 확인해야 하기 때문이다. 이후에는 사각형안에 있는 숫자들을 확인한다. 이때 x, y 값을 3으로 나누고 3을 곱해야 해당 인덱스가 속한 사각형의 우측 상단 인덱스를 얻을 수 있다.

 

 

다음은 DFS 함수이다. 나는 맨 처음에 DFS 함수가 다 끝나면 main 함수에서 스도쿠 결과를 출력하도록 시도했는데 잘못된 방법이었다. 가장 최적의 방법은 스도쿠 모든 칸을 다 확인 했을 때 DFS함수 안에서 출력을 하고 프로그램을 종료하는 것이다. 나는 여기서 exit(0)를 썼는데 만약 DFS를 최초로 호출한 스코프로 돌아가야 한다면 return을 적절하게 추가해야 할거 같다. 만약 아직 모든 스도쿠 칸을 확인을 못했다면 현재 칸의 값을 확인해서 0이 아니라면 다음칸으로 넘어가고 현재 칸이 0으로 비어있다면 1부터 9까지 반복문을 돌면서 가능한 숫자를 확인한다. 이때 가능한 숫자를 확인하면 해당 칸의 숫자를 업데이트하고 다음칸으로 넘어가게 된다.

 

만약 DFS 호출 했는데 return이 되어서 다시 돌아왔다면 이후에 칸에 가능한 숫자가 없다는 뜻이다. 이런 경우에는 업데이트 했던 값을 다시 0으로 되돌리고 남은 반복문을 반복하면서 가능한 숫자를 다시 찾아야 한다. 나는 이부분이 햇갈려서 이해하는데 시간이 오래걸렸다.

 

다음 칸으로 넘어갈 때 주의 사항이 있는데 행과 열을 헷갈리지 않도록 조심해야 한다. 나는 처음에 행과 열을 반대로 증가시켜서 이상한 값이 계속 나와서 원인을 찾느라 애를썼다. y가 가로 인덱스를 나타내기 때문에 y가 8이 됐다면 세로 인덱스 x를 증가시켜야 한다. 그리고 x가 8인상태에서 y또한 8이 된다면 다음 DFS 호출에서 x는 9가 될 것이고 처음에 if문에 걸려서 결과가 출력이 되고 프로그램이 종료될 것이다.

 

 

main 함수는 비교적 간단하다. 하지만 여기서 트릭아닌 트릭이 쓰였는데 가로줄의 입력을 하나의 숫자 문자열로 받기 때문에 각 숫자를 분리해서 저장해야 한다. 그래서 나는 string으로 입력 받고 반복문을 돌면서 char 문자를 가져와서 '0'으로 빼준 값을 넣어줬다. 

이렇게 하면 '0~9 중 하나의 숫자' - '0' 이런 연산을 하게 되는데 이때 두 문자의 아스키 코드 값의 차이가 저장된다. 그러면 복잡하게 형변환을 하지 않고서 string으로 저장된 숫자 문자열에서 하나의 숫자만 정수형으로 저장할 수 있다.