글 읽기 - 반례좀 부탁드립니다..

kino6147 3년 전 0

안녕하세요, 문제의 예시나, 게시판에 있는 여러 반례 글에 대한 테스트로 하였습니다만

정상적으로 답이 나옵니다.

도대체 어떤 반례가 있는지 잘 모르겠습니다. 어떤 반례가 있는지 지식을 공유해주시면 감사하겠습니다.

// https://www.acmicpc.net/problem/2580
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

typedef struct Block {
    int row, col, content;
} Block;

bool done = false;

std::vector<std::vector<int>> sudoku;
std::vector<Block> blankList;
std::vector<Block> stack;


void printSudoku() {
    for(std::vector<int> eachCol : sudoku) {
        for(int each : eachCol) {
            std::cout << each << ' ';
        }
        std::cout << "\n";
    }
}

std::vector<int> getPossibleSolution(Block currentBlock) {
    std::vector<int> ret(9);
    std::iota(ret.begin(), ret.end(), 1);

    // 가로 체크
    for(int each : sudoku[currentBlock.row]) {
        if(each != 0) {
            ret.erase(std::remove(ret.begin(), ret.end(), each), ret.end());
        }
    }

    if(ret.size() == 1) {
        return ret;
    }

    // 세로 체크
    for(int i = 0; i < 9; i++) {
        if(sudoku[i][currentBlock.col] != 0) {
            ret.erase(std::remove(ret.begin(), ret.end(), sudoku[i][currentBlock.col]), ret.end());
        }
    }

    if(ret.size() == 1) {
        return ret;
    }
    
    // 네모 체크
    int startRow = currentBlock.row - (currentBlock.row % 3);
    int startCol = currentBlock.col - (currentBlock.col % 3);
    for(int i = startRow; i < startRow + 3; i++) {
        for(int j = startCol; j < startCol + 3; j++) {
            if(sudoku[i][j] != 0) {
                ret.erase(std::remove(ret.begin(), ret.end(), sudoku[i][j]), ret.end());
            }
        }
    }

    return ret;
}

void DFS() {

    if(done) {
        return;
    } else {
        // 탈출조건명시
        if(blankList.empty()) {
            for(Block solution : stack) {
                // sudoku[solution.row][solution.col] = solution.content;
            }
            printSudoku();
            done = true;
            return;
        }
        Block nextBlock = blankList.back();
        blankList.pop_back();

        for(int possible : getPossibleSolution(nextBlock)) {
            sudoku[nextBlock.row][nextBlock.col] = possible;
            stack.push_back({nextBlock.row, nextBlock.col, possible});
            DFS();
            sudoku[nextBlock.row][nextBlock.col] = 0;
            stack.pop_back();
        }


        blankList.push_back(nextBlock);
    }

    
}


int main() {
    std::cin.tie(NULL);
    std::cin.sync_with_stdio(false);
    blankList.reserve(80);
    sudoku.reserve(9);
    for(int i = 0; i < 9; i++) {
        std::vector<int> col(9);
        for(int j = 0; j < 9; j++) {
            std::cin >> col.at(j);
            if(col.at(j) == 0) {
                blankList.push_back({i, j, 0});
            }
        }
        sudoku.push_back(col);
    }
    DFS();
}

kino6147 3년 전 0

가능한 자식 노드를 찾는 함수 (getPossibleSolution()) 을 실행하는 와중에

먼저 리턴을 하면 빨리 함수를 돌기 때문에 시간 문제를 해결할 수 있을거라 생각하여

if(ret.size() == 1) {
    return ret;
}

을 삽입하였으나 이내 잘못되었다는 사실을 깨달았습니다. 감사합니다.

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

문제

문제

출처

ICPC

반례좀 부탁드립니다..

kino6147 3년 전 0

kino6147 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말