글 읽기 - 시간 초과가 나는 이유가 뭘까요?

seokjeongeum 2년 전 0

그 자리에 그 수가 들어갈 수 있는지를 배열로 관리하여 상수 시간에 알아내고 있고,

dfs끝날 때 exit(0)호출하여 프로그램을 종료하고 있는데

시간 초과가 나는 이유가 뭘까요?

#include <iostream>
#include <vector>
#include <limits>
using namespace std;
int board[9][9];
bool row_availability[9][10];
bool column_availability[9][10];
bool square_availability[3][3][10];
void dfs(int r, int c) {
	if (r == 9) {
		for (int i = 0;i < 9;++i) {
			for (int j = 0;j < 9;++j) {
				cout << board[i][j];
			}
			cout << '\n';
		}
		exit(0);
	}
	if (board[r][c] == 0) {
		for (int i = 1;i <= 9;++i) {
			if (row_availability[r][i] && column_availability[c][i] && square_availability[r / 3][c / 3][i]) {
				row_availability[r][i] = false;
				column_availability[c][i] = false;
				square_availability[r / 3][c / 3][i] = false;
				board[r][c] = i;
				if (c == 8) {
					dfs(r + 1, 0);
				}
				else {
					dfs(r, c + 1);
				}
				row_availability[r][i] = true;
				column_availability[c][i] = true;
				square_availability[r / 3][c / 3][i] = true;
				board[r][c] = 0;
			}
		}
	}
	else {
		row_availability[r][board[r][c]] = false;
		column_availability[c][board[r][c]] = false;
		square_availability[r / 3][c / 3][board[r][c]] = false;
		if (c == 8) {
			dfs(r + 1, 0);
		}
		else {
			dfs(r, c + 1);
		}
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cout.precision(numeric_limits<double>::max_digits10);
	for (int i = 0;i < 3;++i) {
		for (int j = 0;j < 3;++j) {
			for (int k = 1;k <= 9;++k) {
				square_availability[i][j][k] = true;
			}
		}
	}
	for (int i = 0;i < 9;++i) {
		for (int j = 1;j <= 9;++j) {
			row_availability[i][j] = true;
			column_availability[i][j] = true;
		}
	}
	for (int i = 0;i < 9;++i) {
		string s;
		cin >> s;
		for (int j = 0;j < 9;++j) {
			board[i][j] = s[j] - '0';
		}
	}
	dfs(0, 0);
	return 0;
}

pichulia 2년 전 1

시간초과의 원인은 잘 모르겠지만, 일단 틀린 코드입니다.

가장 큰 문제로는, 보드에 적혀있는 숫자를 전혀 활용하지 못하고 있습니다.

아래와 같은 데이터에 대해서 정답을 출력하도록 수정하셔야 할 것 같습니다.

우선 해당 부분에 대한 수정만 하면 정답을 받은 것을 확인했습니다.

seokjeongeum 2년 전 0

감사합니다

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

문제

문제

출처

ICPC

시간 초과가 나는 이유가 뭘까요?

seokjeongeum 2년 전 0

pichulia 2년 전 1

seokjeongeum 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말