글 읽기 - 어디가 잘못된건가요??

asterisk120 5년 전 0

어떤 자리가 0이면 1부터 시작해서 9까지 체크할때 가로줄, 세로줄, 3x3 정사각형 안에 그 수가 있는지 체크하고 없는 수가 존재하면 채우도록 짰는데 이렇게 하면 안되나요??

#include <iostream>

constexpr int MAX = 9;

void filling(int arr[][MAX], int y, int x) {
	int yt = y - y % 3, xt = x - x % 3;
	bool vertCheck, horizCheck, SquarCheck;

	for (int iter = 1; iter <= 9; iter++) {
		vertCheck = false, horizCheck = false, SquarCheck = false;
		for (int i = 0; i < 3; i++)
			for (int j = 0; j < 3; j++) {
				if (arr[y][i + j] == iter)
					vertCheck = true;
				if (arr[i + j][x] == iter)
					horizCheck = true;
				if (arr[yt + i][xt + j] == iter)
					SquarCheck = true;
			}
		if (!vertCheck && !horizCheck && !SquarCheck) {
			arr[y][x] = iter;
			return;
		}
	}
}

int main(void)
{
	int arr[MAX][MAX];

	for (int i = 0; i < MAX; i++)
		for (int j = 0; j < MAX; j++)
			scanf("%d", &arr[i][j]);

	for (int i = 0; i < MAX; i++)
		for (int j = 0; j < MAX; j++)
			if (!arr[i][j])
				filling(arr, i, j);

	for (int i = 0; i < MAX; i++) {
		for (int j = 0; j < MAX; j++)
			printf("%d ", arr[i][j]);
		printf("\n");
	}
}

djm03178 5년 전 2

스도쿠를 해보셨다면, 그렇게 무작정 지금 당장 되는 걸로 채우면 답이 나오지 않는 경우가 생긴다는 걸 아실 것입니다.

asterisk120 5년 전 0

음.. 스도쿠를 안해봐서;; 쨌든 논리가 문제였군요.. 감사합니다!

djm03178 5년 전 1

기본적인 접근법은 지금이랑 비슷하긴 합니다. 다만, 이 문제는 백트래킹 문제이므로 답이 나오지 않는다는 것을 발견했을 때 뒤로 돌아가서 다른 가능한 경우의 수도 시도해보는 것이 정해입니다.

asterisk120 5년 전 0

아하 그렇군요.. 힌트 감사합니다~

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

어디가 잘못된건가요??

asterisk120 5년 전 0

djm03178 5년 전 2

asterisk120 5년 전 0

djm03178 5년 전 1

asterisk120 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말