문제

문제접근

문제 이해

• 이전에 풀이했던 '스도쿠'문제 알고리즘 :: 백준 :: Bruteforce :: 2580 :: 스도쿠 (velog.io) 의 연장선입니다.

• 기본 골자는 거의 같지만, 이번에는 가로 2칸 또는 세로 2칸으로 도미노를 놓아야 한다는 점이 다릅니다.

• 이번에는 저번 풀이와는 다르게 진행하겠습니다.

  1. 빈칸을 따로 저장하지 않고 0번째 칸부터 81번째 칸까지 모두 순회하면서 재귀를 수행하는 방법을 사용하겠습니다.

  2. row, col 그리고 group에 어떤 숫자가 들어있는지 표현하는 외부 bool타입 배열 rowNum[9][10], colNum[9][10] 그리고 groupNum[9][10]을 만들었습니다.

• 임의의 (y, x)칸이 0으로 빈칸이 확인됐을 경우, 도미노를 놓을 수 있는 방법은 두 가지 입니다.

  1. 가로로 놓습니다. 이때 (y, x + 1)이 빈칸이 아니라면 놓을 수 없습니다.
  2. 세로로 놓습니다. 이때 (y + 1, x)이 빈칸이 아니라면 놓을 수 없습니다.

• domino[10][10] 이라는 배열을 만들었습니다. 이 2차원 배열은 i와 j 조합 도미노를 의미합니다.
  만일 (1, 3) 이라는 도미노를 썼다면, domino[1][3] = domino[3][1] = true입니다.

• 이전 문제와는 다르게 이번에는 재귀함수 solve의 반환형이 void가 아니라 bool 타입입니다. 이는 수행속도를 줄이기 위함입니다. 우리는 이 문제에서 가능한 경우를 단 한 번만 출력하면 되기 때문에 가능한 경우를 찾았다면 더 이상 진행하지 않아도 됩니다.

• 나머지 로직은 모두 이전 문제(도미노)와 동일합니다.
  코드를 보시면, 쉽게 이해하실 수 있습니다.

코드

#include <iostream>
#include <cstring>
using namespace std;

int sudoku[9][9], d[2][2] = {{0, 1}, {1, 0}};
bool domino[10][10], rowNum[9][10], colNum[9][10], groupNum[9][10];

void initialize() {
	memset(rowNum, false, sizeof(rowNum));
    memset(colNum, false, sizeof(colNum));
    memset(groupNum, false, sizeof(groupNum));
    memset(domino, false, sizeof(domino));
    memset(sudoku, 0, sizeof(sudoku));
}

void checkNum(int y, int x, int num, bool type) {
	rowNum[y][num] = colNum[x][num] = groupNum[(y / 3) * 3 + (x / 3)][num] = type;
}

bool isValid(int y, int x, int num) {
	return (!rowNum[y][num] && !colNum[x][num] && !groupNum[(y / 3) * 3 + (x / 3)][num]);
}

bool solve(int cnt) {
	if (cnt == 81) {
		for (int i = 0; i < 9; ++i) {
			for (int j = 0; j < 9; ++j)
				cout << sudoku[i][j];
			cout << '\n';
		} return true;
	}
	int cy = cnt / 9, cx = cnt % 9;
	if (sudoku[cy][cx] != 0) return solve(cnt + 1);
	for (int k = 0; k < 2; ++k) {
		int ny = cy + d[k][0], nx = cx + d[k][1];
		if (ny < 0 || nx < 0 || ny >= 9 || nx >= 9) continue;
		if (sudoku[ny][nx] != 0) continue;
		for (int i = 1; i <= 9; ++i)
			for (int j = 1; j <= 9; ++j) {
				if (i == j || domino[i][j]) continue;
				if (!isValid(cy, cx, i) || !isValid(ny, nx, j)) continue;
				// Check for this loop
				checkNum(cy, cx, i, true);
				checkNum(ny, nx, j, true);
				domino[i][j] = domino[j][i] = true;
                		sudoku[cy][cx] = i;
                		sudoku[ny][nx] = j;
                		// Go for backtracking
				if (solve(cnt + 1)) return true;
                		// Uncheck for next loop
                		checkNum(cy, cx, i, false);
				checkNum(ny, nx, j, false);
				domino[i][j] = domino[j][i] = false;
                		sudoku[cy][cx] = 0;
                		sudoku[ny][nx] = 0;
			}
	}
	return false;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int tc = 1;
	while (true) {
		int N;
		cin >> N;
		if (N == 0) break;
		
		int n1, n2, y1, x1, y2, x2;
		string pos, pos1, pos2;
		for (int i = 0; i < N; ++i) {
			cin >> n1 >> pos1 >> n2 >> pos2;
			y1 = pos1[0] - 'A', x1 = pos1[1] - '1';
			y2 = pos2[0] - 'A', x2 = pos2[1] - '1';
			sudoku[y1][x1] = n1;
			sudoku[y2][x2] = n2;
			domino[n1][n2] = domino[n2][n1] = true;
			checkNum(y1, x1, n1, true);
			checkNum(y2, x2, n2, true);
		}
		for (int i = 1; i <= 9; ++i) {
			cin >> pos;
			y1 = pos[0] - 'A', x1 = pos[1] - '1';
			sudoku[y1][x1] = i;
			checkNum(y1, x1, i, true);
		}
		cout << "Puzzle " << tc++ << '\n';
		solve(0);
		initialize();
	}
}

결과