글 읽기 - 고수님들 바쁘신 거 알지만 한 번만 도와주십시오

mywonkim 3년 전 2

웬만한 건 다 했다고 느껴지지만, 시간 초과가 나오고 있습니다. check하는 함수들이 문제일까요...

#include <bits/stdc++.h>
using namespace std;

int mp[9][9];

bool checkOneRow(int row, int toput) {
    for (int col = 0; col < 9; ++col) {
        if (mp[row][col] == toput) return false;
    }
    return true;
}

bool checkOneCol(int col, int toput) {
    for (int row = 0; row < 9; ++row) {
        if (mp[row][col] == toput) return false;
    }
    return true;
}

bool checkOneBox(int row, int col, int toput) {
	int rstart = row / 3 * 3;
	int cstart = col / 3 * 3;
	for (int r = rstart; r < rstart + 3; ++r) {
        for (int c = cstart; c < cstart + 3; ++c) {
            if (mp[r][c] == toput) return false;
        }
    }
    return true;
}

void solveSudoku(int zerocnt, int cnt) {
    if (cnt == zerocnt) {
    	for (int i = 0; i < 9; ++i) {
    		for (int j = 0; j < 9; ++j) {
    			cout << mp[i][j] << " ";
			}
			cout << "\n";
		}
		exit(0);
    }
    for (int i = 0; i < 9; ++i) {
        for (int j = 0; j < 9; ++j){
            if (mp[i][j] == 0) {
                for (int k = 1; k <= 9; ++k) {
                	if (checkOneRow(i, k) &&
                        checkOneCol(j, k) &&
                        checkOneBox(i, j, k)) {
                        mp[i][j] = k;
                        solveSudoku(zerocnt, cnt + 1);
                        mp[i][j] = 0;
                    }
                }
            } 
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int zerocnt = 0;
    for (int i = 0; i < 9; ++i) {
        for (int j = 0; j < 9; ++j) {
            cin >> mp[i][j];
            if (mp[i][j] == 0) ++zerocnt;
        }
    }
    solveSudoku(zerocnt, 0);
}

malratz 3년 전 2

각 행, 열, 그룹에서 특정 숫자가 쓰였는지에 대해서 O(1) 만에 확인 하는 방법이 있습니다.

mywonkim 3년 전 1

추가로 저는 재귀를 할 때마다 2중 for loop을 돌았는데 생각해보니까 그럴 필요 없이 각 좌표를 딱 한 번씩만 돌면 되더라고요. 답변 감사합니다!

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

문제

문제

출처

ICPC

고수님들 바쁘신 거 알지만 한 번만 도와주십시오

mywonkim 3년 전 2

malratz 3년 전 2

mywonkim 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말