글 읽기 - 문제점을 못찾겠습니다ㅠㅜ

younga 4년 전 0

문제에서 제공된 테스트 케이스는 돌아가는데 모두 0인 케이스에서는 돌아가지 않네요 ㅠㅠㅠ

왜 그런지 너무 모르겠어서 질문드립니다.

다른 소스코드들도 모두 보았는데

많은 분들이 0부터 81번쨰까지 모두 dfs를 도는 식으로 구현하신것 같더라고요

저는 먼저 0인 부분을 먼저 벡터에 넣고 0인 부분만 dfs를 돌려고하는데

어느 부분이 잘못된 걸까요??

#include<iostream>
#include<vector>
#define endl "\n"
#define MAX 9
using namespace std;

int map[9][9];
bool row[9][9];
bool col[9][9];
bool square[9][9];
vector<pair<int, int>>blank;


void sdoku(int idx) {
	if (idx == blank.size()) {
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				cout << map[i][j] << " ";
			}cout << endl;
		}
		exit(0);
		return;
	}

	for (int i = 0; i < blank.size(); i++) {
	    
        /*
        이 부분이 문제라 생각되어 추가해보았지만 값이 출력되지않습니다 ㅠㅠㅠ
        
        if(visit[i])continue;
		visit[i] = true;
        */
        
		for (int k = 1; k <= 9; k++) {
			if (row[blank[i].first][k] == false && col[blank[i].second][k] == false 
                && square[ (blank[i].first/3 *3)+ blank[i].second/3][k] == false) {
	
				row[blank[i].first][k] = true;
				col[blank[i].second][k] = true;
				square[(blank[i].first / 3 * 3) + blank[i].second / 3][k] = true;
				map[blank[i].first][blank[i].second] = k;
				
                sdoku(idx + 1);
				
                row[blank[i].first][k] = false;
				col[blank[i].second][k] = false;
				square[(blank[i].first / 3 * 3) + blank[i].second / 3][k] = false;
				map[blank[i].first][blank[i].second] = 0;

			}
		}
		
	}

}

int main() {
	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			cin >> map[i][j];
			if (map[i][j] == 0) {
				blank.push_back(make_pair(i, j));
			}
			else{
				row[i][map[i][j]] = true;
				col[j][map[i][j]] = true;
				square[(i / 3)*3 + j / 3][map[i][j]] = true;

			}
		}
	}
	sdoku(0);
	return 0;
}

pichulia 4년 전 0

크기가 N인 배열의 인덱스는 0부터 N-1까지입니다.

그리고 굳이 i부터 다 돌 필요 없의 i = idx라고만 해도 충분해보입니다.

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

문제

문제

출처

ICPC

문제점을 못찾겠습니다ㅠㅜ

younga 4년 전 0

pichulia 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말