글 읽기 - 백트랙킹 초보자입니다.

sotter1020 5년 전 0

다른 분들과 코드 비교해봐도 비슷한거 같은데

어떤 부분이 틀렸는지 잘 모르겠습니다..

#include<iostream>
#include<vector>
using namespace std;
int board[9][9];
vector<pair<int, int>> zero;
bool isPossible(int y, int x) {
    // 세로 가로 대각선중에 중복되면 false리턴
	vector<vector<bool>> num(3, vector<bool>(10, false));
	for (int h = 0; h < 9; ++h) {
		if (board[y][h] == 0) continue;
		if (num[0][board[y][h]]) return false;
		else num[0][board[y][h]] = true;
		if (board[h][x] == 0) continue;
		if (num[1][board[h][x]]) return false;
		else num[1][board[h][x]] = true;
	}
	int sy = y / 3 * 3, sx = x / 3 * 3;
	for (int i = sy; i < sy+ 3; ++i)
		for (int j = sx; j < sx + 3; ++j) {
			if (board[i][j] == 0) continue;
			if (num[2][board[i][j]]) return false;
			else num[2][board[i][j]] = true;
		}
	return true;
}
bool dfs(int here) {
	if (here == zero.size()) return true;
	int y = zero[here].first;
	int x = zero[here].second;
	for (int i = 1; i <= 9; ++i) {
		board[y][x] = i;
		if (isPossible(y, x))
			if (dfs(here + 1)) return true;
	}
	board[y][x] = 0;
	return false;
}
int main() {
	for (int y = 0; y < 9; ++y) for (int x = 0; x < 9; ++x) {
		cin >> board[y][x];
		if (board[y][x] == 0)
			zero.push_back({ y,x });
	}
	dfs(0);
	for (int y = 0; y < 9; ++y) {
		for (int x = 0; x < 9; ++x)
			cout << board[y][x] << ' ';
		cout << endl;
	}
	return 0;
}

seico75 5년 전 0

반례로 알려드리고 싶지만, 수도쿠는 넘 어렵네요. ㅠㅠ

10과 13라인이 만일 0일 경우는 뭐라도 와도된다는 거일텐데..

10라인이 만족하면 13 라인 이하도 건너뛰어서 만족하지 않아도 만족한다고 할 가능성이 있네요.

그런데... 시간초과가 나오네요.

sotter1020 5년 전 0

아! 감사합니다! 시간초과나는건 해결 할 수 있을거 같습니다!

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

문제

문제

출처

ICPC

백트랙킹 초보자입니다.

sotter1020 5년 전 0

seico75 5년 전 0

sotter1020 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말