글 읽기 - 전체 0 테스트케이스를 통과하는 방법을 알고 싶습니다ㅠ

applied7076 4년 전 0

입력 시에 0인 부분을 받아서 queue에 좌표를 넣은 뒤 하나씩 꺼내면서 세로, 가로, 3x3 검사를 하면서 숫자를 채우는 식으로 짰는데요..

(1~9까지 넣고 검사가 충족하지 않을 시 0으로 다시 되돌리고 queue에 다시 넣어요)

0 3 0 4 6 9 2 7 8 
7 8 2 1 3 5 6 4 9 
4 6 9 2 7 8 1 3 5 
0 2 0 5 4 6 8 9 7 
8 7 4 9 1 3 5 2 6 
5 9 6 8 2 7 4 1 3 
9 1 7 6 5 2 3 8 4 
6 4 3 7 8 1 9 5 2 
2 5 8 3 9 4 7 6 1 
2 5 8 3 9 4 7 6 0

이런 테스트케이스는 통과하는데 전체가 0인 테스트케이스는 벗어나지를 못해요

좋은 해결 방법 있을까요?

#include <iostream>
#include <queue>
#include <utility>
#define y first
#define x second
using namespace std;
int v[9][9];
queue<pair<int, int>> zero;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    for (int i=0; i<9; i++) {
        for (int j=0; j<9; j++) {
            cin >> v[i][j];
            if (!v[i][j]) zero.emplace(i, j);
        }
    }
    while (!zero.empty()) {
        pair<int, int> tmp = zero.front();
        zero.pop();
        auto cy = tmp.y;
        auto cx = tmp.x;
        //cout << cy < < ", " << cx << '\n';
        bool found = false;
        for (int k=1; k<=9; k++) {
            v[cy][cx] = k;
            auto by = cy/3*3;
            auto bx = cx/3*3;
            for (int i=0; i<9; i++) { //세로 검사
                if (cy == i) continue;
                if (v[cy][cx] == v[i][cx]) goto back;
            }
            for (int j=0; j<9; j++) { //가로 검사
                if (cx == j) continue;
                if (v[cy][cx] == v[cy][j]) goto back;
            }
            for (int i=0; i<3; i++) {
                for (int j=0; j<3; j++) { //3x3
                    if (cy == by+i && cx == bx+j) continue;
                    if (v[cy][cx] == v[by+i][bx+j]) goto back;
                }
            }
            found = true;
            //cout << "[ " << k << " ]" << '\n'; //
            break;
            back:
            continue;
        }
        if (!found) {
            v[cy][cx] = 0;
            zero.emplace(cy, cx);
        }
    }
    for (auto & i : v) {
        for (int j : i) cout << j << ' ';
        cout << '\n';
    }
}

djm03178 4년 전 1

이러한 방법이 시간 내에 된다는 이야기는 들은 적이 없습니다. 평범하게 다른 사람들처럼 DFS로 구현하시는 게 어떨까요?

applied7076 4년 전 0

네 그럼 DFS로도 한 번 짜보겠습니다 조언 감사드려요

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

문제

문제

출처

ICPC

전체 0 테스트케이스를 통과하는 방법을 알고 싶습니다ㅠ

applied7076 4년 전 0

djm03178 4년 전 1

applied7076 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말