글 읽기 - 어느 부분이 틀린지 잘 모르겠습니다.

glanceyes 4년 전 0

예제와 질문 게시판에 올라온 반례 모두 실행해봤는데, 어느 부분이 논리적으로 오류가 있는 건지 잘 모르겠습니다.

가로, 세로, 3X3 정사각형에 각각 어떤 숫자가 미리 존재하는지를 저장하기 위해 check1, check2, check3를 사용했고, 스도쿠에서 숫자를 채워야할 좌표는 fillblank에 넣어서 백트래킹 방식으로 진행했습니다.

실력이 부족한지라 어느 부분이 잘못되었는지 알려주시면 감사드립니다.

#include <cstdio>
#include <vector>

using namespace std;

int fillnum;
int sudo[9][9];
bool finishflag;
bool check1[9][9]; // 가로
bool check2[9][9]; // 세로
bool check3[3][3][9]; // 3 X 3 정사각형
vector<pair<pair<int, int>, int>> fillblank; // 앞에는 좌표, 뒤에는 값

void fill(int idx) {
    if (idx == fillnum) {
        for (int i = 0; i < fillnum; i += 1) {
            int tempx = fillblank[i].first.first;
            int tempy = fillblank[i].first.second;
            int tempvalue = fillblank[i].second;
            sudo[tempx][tempy] = tempvalue;
        }
        finishflag = true;
        return;
    }
    for (int i = 1; i < 10; i += 1) {
        int temp1 = fillblank[idx].first.first;
        int temp2 = fillblank[idx].first.second;
        if (!check1[temp1][i] && !check2[temp2][i] &&
            !check3[temp1 / 3][temp2 / 3][i]) {
            fillblank[idx].second = i;
            check1[temp1][i] = check2[temp2][i] = true;
            check3[temp1 / 3][temp2 / 3][i] = true;
            fill(idx + 1);
            if (finishflag) return;
            fillblank[idx].second = 0;
            check1[temp1][i] = check2[temp2][i] = false;
            check3[temp1 / 3][temp2 / 3][i] = false;
        }
    }
}

int main() {
    for (int i = 0; i < 9; i += 1) {
        for (int j = 0; j < 9; j += 1) {
            scanf("%d", &sudo[i][j]);
            if (!sudo[i][j]) {
                fillblank.push_back(make_pair(make_pair(i, j), 0));
                fillnum += 1;
            }
            else {
                check1[i][sudo[i][j]] = true;
                check2[j][sudo[i][j]] = true;
                check3[i / 3][j / 3][sudo[i][j]] = true;
            }
        }
    }

    fill(0);

    for (int i = 0; i < 9; i += 1) {
        for (int j = 0; j < 9; j += 1) {
            printf("%d ", sudo[i][j]);
        }
        printf("\n");
    }
    return 0;
}

glanceyes 4년 전 0

자문자답입니다.

어이없게도 check3의 인덱스 범위를 1부터 9까지를 포함되도록 10으로 잡아야 하는데 9로 잡아서 틀렸네요...

수정해서 돌렸더니 됩니다. 죄송합니다.

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

문제

문제

출처

ICPC

어느 부분이 틀린지 잘 모르겠습니다.

glanceyes 4년 전 0

glanceyes 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말