글 읽기 - 시간초과 도와주세요!

sungdd2 4년 전 0

어떻게 풀까 고민하다가, 그냥 제가 스도쿠를 푸는 흐름 그대로를 코드로 구현했습니다.

가로로 쭉 보면서 9칸 중 1칸이 비어있는게 있다면 채우고 (처음부터 마지막 칸까지)

세로를 보면서 위와 똑같이 하고,

그 다음에 3*3칸을 보면서 채우고.

물론 없다면 넘어가고 이 가로,세로,3*3 과정을 for문으로 무한 반복으로 돌리면서 빈 칸이 없다면 종료하기.

이게 대략적인 흐름입니다.

물론 구글링하거나 질문글들 검색하면 어떻게 푸는지, 해결해야 하는지 알 수 있습니다만,

뭔가 열심히 짰는데 다 엎고 다시 풀기가 너무 아쉽더라구요

혹시 제가 짠 코드에서 어떻게 잘 만져서 정답으로 될 수 있는 방법은 없을까요??

#include <iostream>

using namespace std;

int map[10][10];
int arr[9];
bool row();
bool col();
int cir();
int miarr(int i, int j);
int circal(int x, int y);

int main() {
	ios_base::sync_with_stdio(false);
	int cnt = 0;

	for (int i = 0; i < 9; i++) {
		cnt = 0;
		for (int j = 0; j < 9; j++) {
			cin >> map[i][j];
			if (map[i][j] == 0)
				cnt++;
		}
		map[i][9] = cnt;
	}

	for (int i = 0; i < 9; i++) {
		cnt = 0;
		for (int j = 0; j < 9; j++) {
			if (map[j][i] == 0)
				cnt++;
		}
		map[9][i] = cnt;
	}

	cnt = 0;
	for (int i = 0; i < 9; i++) {
		cnt += map[i][9];
		cnt += map[9][i];
	}
	map[9][9] = cnt;
	int index = 0;

	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			cnt = 0;
			for (int k = 0; k < 3; k++) {
				for (int w = 0; w < 3; w++) {
					if (map[3 * i+k][3 * j+w] == 0)
						cnt++;
				}
			}
			arr[index++] = cnt;
		}
	}


	for (;;) {
		if (row())
			continue;
		if (map[9][9] == 0)
			break;
		if (col())
			continue;
		if (map[9][9] == 0)
			break;
		cir();
		if (map[9][9] == 0)
			break;
	}

	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			cout << map[i][j] << " ";
		}
		cout << '\n';
	}

	return 0;
}

int miarr(int i, int j) {
	//i,j를 통해 arr에서 1제거.
	if (i < 3) {
		if (j < 3)
			arr[0]--;
		else if (j < 6)
			arr[1]--;
		else
			arr[2]--;
	}
	else if (i < 6) {
		if (j < 3)
			arr[3]--;
		else if (j < 6)
			arr[4]--;
		else
			arr[5]--;
	}
	else {
		if (j < 3)
			arr[6]--;
		else if (j < 6)
			arr[7]--;
		else
			arr[8]--;
	}

	return 0;
}

bool row() {
	
	bool check = false;

	for (int i = 0; i < 9; i++) {
		if (map[i][9] == 1) {
			check = true;
			int tmp = 0; int cnt = 45;
			for (int j = 0; j < 9; j++) {
				if (map[i][j] == 0) {
					tmp = j;
					continue;
				}
				else
					cnt -= map[i][j];
			}
			map[i][tmp] = cnt;
			map[i][9] = 0;
			map[9][tmp]--;
			map[9][9] -= 2;
			miarr(i, tmp);
		}
	}

	return check;
}

bool col() {

	bool check = false;

	for (int i = 0; i < 9; i++) {
		if (map[9][i] == 1) {
			check = true;
			int tmp = 0; int cnt = 45;
			for (int j = 0; j < 9; j++) {
				if (map[j][i] == 0) {
					tmp = j;
					continue;
				}
				else
					cnt -= map[j][i];
			}
			map[tmp][i] = cnt;
			map[9][i] = 0;
			map[tmp][9]--;
			map[9][9] -= 2;
			miarr(i, tmp);
		}
	}

	return check;
}

int cir() {

	for (int i = 0; i < 9; i++) {
		if (arr[i] == 1) {
			int k = i / 3;
			int w = i % 3;
			circal(3 * k, w * 3);
		}
	}

	return 0;
}

int circal(int x, int y) {

	int tmp_i, tmp_j;
	int cnt = 45;

	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			if (map[i + x][j + y] == 0) {
				tmp_i = i + x;
				tmp_j = j + y;
				continue;
			}
			else
				cnt -= map[i + x][j + y];
		}
	}

	map[9][9] -= 2;
	map[tmp_i][tmp_j] = cnt;
	map[tmp_i][9]--;
	map[9][tmp_j]--;
	miarr(tmp_i, tmp_j);

	return 0;
}

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

문제

문제

출처

ICPC

시간초과 도와주세요!

sungdd2 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말