백준 2239 - 스도쿠

https://www.acmicpc.net/problem/2239

2239번: 스도쿠

문제에서 요구하는 대로 성실하게 백트래킹을 구현하면 된다.

개인적으로 이런 백트래킹 문제는 백준 "N과 M" 시리즈를 풀고 나면 더 쉽게 접근할 수 있을 듯 하다.

 

0. '스도쿠 규칙' 구현

9x9 스도쿠는 "각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다" 라는 규칙을 가진다.

 

따라서 규칙대로 행, 열, 3x3 사각형 내부에 1~9가 이미 존재하는 가를 판별하는 3가지의 visited 배열을 선언한다.

//R[i][j] : i행에 j가 이미 있는가?
vector<vector<bool>> R(N + 1, vector<bool>(N + 1));

//C[i][j] : i열에 j가 이미 있는가?
vector<vector<bool>> C(N + 1, vector<bool>(N + 1));

//SQ[i][j] : i번 사각형에 j가 이미 있는가?
vector<vector<bool>> SQ(N + 1, vector<bool>(N + 1));

i번 사각형은 왼쪽 맨 위 사각형을 1번으로 1~9까지 번호를 부여했다. row행 col열 좌표가 속한 사각형을 구하는 함수는 다음과 같이 설정했다.

int findSQ(int row, int col) {
	return 1 + (row - 1) / 3 * 3 + (col - 1) / 3;
}

 

1. 초기화

9x9 보드를 입력받아 저장한다. 보드를 순회하며, 문자값이 '0'이 아닌 위치마다 그에 해당하는 R, C, SQ 인덱스에 해당 숫자가 이미 존재한다고 표시한다.

 

문제의 입력을 예시로, R[1], C[1], SQ[1] 배열의 값만 살펴보자.

input
103000509
002109400
000704000
300502006
060000050
700803004
000401000
009205800
804000107

//1행에는 1, 3, 5, 9가 존재
R[1][1] ~ R[1][9]
{1,0,1,0,1,0,0,0,1}

//1열에는 1, 3, 7, 8이 존재
C[1][1] ~ C[1][9]
{1,0,1,0,0,0,1,1,0}

//1번 사각형에는 1, 2, 3이 존재
SQ[1][1] ~ SQ[1][9]
{1,1,1,0,0,0,0,0,0}

 

2. 순회

왼쪽 위에서 1행부터 9행까지 순회한다. 현재 위치까지는 모든 칸이 스도쿠의 조건에 맞게 0이 아닌 숫자로 채워졌다고 가정하고(제대로 구현했으면 실제로 그렇다), 현재 위치 이후에 처음으로 등장하는 0의 위치를 찾는다.

 

만약 9행 9열까지 확인했는데 0이 없었다면 스도쿠가 완성됐으므로 현재 배열을 출력하고, 더이상의 재귀호출은 중단시킨다. 함수 초입에 if (found) return; 라고 띡 써놓으면 편하다.

 

3. 재귀함수 호출

배열을 순회하다 0을 발견하면, 해당 위치 {row, col}에 대해 1부터 9까지 숫자를 넣었을 때 행, 열, 사각형 중복이 있는 지 확인한다. 즉, R[row][number], C[col][number], SQ[findSQ(row, col)][number] 값 중 하나라도 1이 있는지 확인한다.

 

어느 하나도 중복이 없다면 키고 들어갔다가 나와서 끄기 를 수행한다. 요게 뭐냐면 백트래킹의 기본적인 구현 방식인데 그냥 내가 이해하기 쉽게 직관적으로 붙인 이름이다.

코드로 보는 게 이해가 더 편할테니 아래 코드를 보자.

//행, 열, 사각형 중복이 없을 경우
if (!R[nr][num] && !C[nc][num] && !SQ[findSQ(nr, nc)][num]) {

	//켜기
    v[nr][nc] = num + '0';
    R[nr][num] = C[nc][num] = SQ[findSQ(nr, nc)][num] = 1;
	
    //들어가기
    recursion(nr, nc);
    
    //나오면 (recursion의 수행이 끝나고 다음 문장을 수행)
	
    //끄기
    v[nr][nc] = '0';
    R[nr][num] = C[nc][num] = SQ[findSQ(nr, nc)][num] = 0;
}

4. 시간초과 해결

백트래킹 문제에서 구현은 잘했는데 왜 시간초과가 뜨지? 싶으면 현재 진행 상황을 얕은 복사 (call by value, 매 호출마다 배열 값을 하나하나 복사)로 전달하고 있는 지 확인해보고,

 

얕은 복사 없이는 백트래킹을 절대 구현할 수 없는 경우가 아니라면 무조건 깊은 복사 (call by reference, 참조 연산자를 사용해 배열 자체를 전달하므로 값 복사는 생략)로 전달하자. 전역 변수를 사용해도 된다.

 

애초에 그래야만 하는 경우가 있는 지도.. 아직은 PS 가방끈이 짧아서 못 봤다. 일반적으로 토글 (키기, 끄기)를 사용하면 원 배열의 값이 변동돼도 백트래킹이 정상적으로 수행된다.