문제개요

• 문제 이름 : 2580, 스도쿠
• 백준 스도쿠 바로가기

스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 일부 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다.

나머지 빈 칸을 채우는 방식은 다음과 같다.

각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
위의 예의 경우, 첫째 줄에는 1을 제외한 나머지 2부터 9까지의 숫자들이 이미 나타나 있으므로 첫째 줄 빈칸에는 1이 들어가야 한다.

또한 위쪽 가운데 위치한 3x3 정사각형의 경우에는 3을 제외한 나머지 숫자들이 이미 쓰여있으므로 가운데 빈 칸에는 3이 들어가야 한다.

이와 같이 빈 칸을 차례로 채워 가면 다음과 같은 최종 결과를 얻을 수 있다.

게임 시작 전 스도쿠 판에 쓰여 있는 숫자들의 정보가 주어질 때 모든 빈 칸이 채워진 최종 모습을 출력하는 프로그램을 작성하시오.

문제 복기

시간 초과

해당 문제는 스도쿠를 해결한 출력을 시간제한 1초 안에 완성해야했다.

코드는 백트래킹을 기본적인 방법으로 작성하였으며,
81개의 스도쿠 칸의 목록을 순회하면서, 3개의 boolean 배열로 열, 행, 칸의 제약 조건을 만족하는지 검사하고, 만족한다면 다음 스도쿠 칸으로 순회, 아니라면 새로운 숫자를 탐색하는 방향으로 작성되었다.

그런데 해당 문제를 해결하는 과정 속에서 시간 초과가 발생하였다.

시간 초과에서 개선한 3가지 방향

1. 조기 리턴을 별도의 변수를 수행하여, 완료가 되었을 때 추가적인 연산을 방지
2. boolean 배열을 활용하여 각 칸에 넣을 수 있는 숫자의 탐색을 좀 더 간편하게
3. 0(빈칸)의 좌표를 별도의 배열로 저장하여 순회 횟수를 감소

시간복잡도 계산

시간 복잡도를 계산할 때 시간 제한 1초당 약 1억번의 연산횟수를 기준으로 삼는다고 한다.

나의 경우 백트래킹이 있기에 연산이 좀더 복잡해지지만, 대략적으로

모든 칸의 순회 + 한번의 스도쿠 탐색 연산 : (9 * 9 * C)
백트래킹 경우의 수 : 최악의 경우 약 5^81(평균적인 경우의수 ^ (스도쿠 칸의 개수))

그러나 해당 문제는 스도쿠를 작성할 때 이렇게 탐색 횟수가 많은 예시를 주지 않는다는 제약조건이 발생하여, 최악의 탐색횟수를 가정하지 않아도 되었다.

다만 반대로 시간복잡도 계산을 어떻게 수행할지 감이 잡히지 않아, 연산을 최적화하는데 중점을 주었다

추가적으로 개선이 가능해보이는 부분

1. 제약조건 검색을 더 빠르게

기존코드

for(int k = 0; k < 9; k++){
    if(this.rows[i][k] || this.cols[j][k] || this.blocks[(i / 3) * 3 + (j / 3)][k]) continue;   

개선코드

int candidates = this.rowMask[i] | this.colMask[j] | this.boxMask[(i/3) * 3 + (j / 3)];
candidates = (~candidates) & 0x3FE;

for(int mask = candidates; mask != 0; mask &=(mask - 1)){
    int bit = mask & -mask;
    int digit = Integer.numberOfTrailingZeros(bit);
        

지금은 각 제약조건을 boolean 배열로 저장하여 순회하여 검사하는 방식을 채택했지만, 이를 비트 연산으로 변경하면 실제 제약을 만족하는 숫자만 탐색이 가능해
9+9+9 의 탐색을 만족하는 숫자만 탐색으로 줄일 수 있다.

2. 경우의 수가 작은 부분부터 탐색

현재는 그냥 0이 0,0->9,9로 갈 때 순서로 위치가 저장되지만 스도쿠 제약조건에 따라 넣어야하는 숫자가 적은 칸부터 탐색을 수행하면 더 적게 순회를 수행할 수 있다.

기존 결과

개선된 코드를 적용한 결과

176ms 결과(방법론 1+2) 가 가장 효율적인 코드로 보이지만,
실제 실행 결과는 방법론 1만 적용하고, 정리되지 않은 레거시 코드가 남아 있는 버전(164ms) 이 오히려 가장 빠른 속도를 보였다.

GPT의 의견이라 확실하지 않지만, 이는 단순히 알고리즘 복잡도 차이가 아니라, Java JIT(Just-In-Time) 컴파일러의 최적화 방식이
실제 실행 속도에 더 큰 영향을 미친 결과로 보인다.

오히려 사용하지 않는 메서드를 넣음으로써 JAVA 실행기에서 자주 사용되는 함수를 빠르게 호출하는 것이 중요하다고 인식하게 만들어, 컴파일되게 만듬으로써 속도가 빨라지는 것 같다는 의견을 남겼다.

따라서 정리되지 않은 코드를 다시 넣어서 최종테스트를 수행해본 결과 168ms의 결과가 나왔다.

레거시 코드가 남은 상황이 오히려 속도를 빠르게 만드는 것이 신기한 상황이었다.

레거시 코드가 없다면 1+2를 동시에 사용하는 것이, 레거시 코드가 있다면 2가 있는 쪽이 오히려 느려진다. 다만 가장 최적의 상황은 레거시 코드가 있는 상황에서 빠르게 연산되는 메소드가 있을 때 오히려 Sorting을 하는 과정이 더 디메리트를 줬다.

1. 더 빠른 연산 순서를 위해 둔 정렬 코드가 이번과 같은 빠른 탐색의 제한이 사전에 주어진 케이스에선 디메리트로 작용할 수 있다는 것
2. 알고리즘만이 아닌 Java 코드 실행기에 의해 코드가 빨라질 수 있다는 것

2가지 신기한 사실을 볼 수 있는 문제였다.