글 읽기 - 코드관련질문입니다.(참고자료)

ggggjin99 1년 전 0

이 코드에서 DFS함수가 빈칸을 계속해서 채우게 되고 line 21의 x == 9일 때 출력을 하고 값을 리턴하는 과정에 있어서,

line 38의 return 0이 실행되는 경우가 있을까요?

간단히 말해 testcase를 입력하였을 때 line 38이 실행이 될까요??

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
using namespace std;

int v[9][9];

bool Check(int x, int y) {
	for (int i = 0; i < 9; i++) {
		if (i != x && v[x][y] == v[i][y]) return 0;
		if (i != y && v[x][y] == v[x][i]) return 0;
	}
	for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) {
		const int cx = x / 3 * 3 + i;
		const int cy = y / 3 * 3 + j;
		if (!(x == cx && y == cy) && v[x][y] == v[cx][cy]) return 0;
	}
	return 1;
}

bool DFS(int x, int y) {
	if (x == 9) {
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) cout << v[i][j] << ' ';
			cout << '\n';
		}
		return 1;
	}
	int nx = x, ny = y + 1;
	if (ny >= 9) nx++, ny = 0;
	if (v[x][y]) return DFS(nx, ny);
	for (int i = 1; i <= 9; i++) {
		v[x][y] = i;
		if (Check(x, y) && DFS(nx, ny)) return 1;
		//if (Check(x, y)){
           // if(DFS(nx, ny)) return 1;
		//}
		v[x][y] = 0;
	}
	return 0;
}

int main() {
	fastio;
	for (int i = 0; i < 9; i++) for (int j = 0; j < 9; j++) cin >> v[i][j];
	DFS(0, 0);
}

// 출처 :https://blog.naver.com/PostList.naver?blogId=jinhan814

munhwas1140 1년 전 0

만약에

1 2 3 4 0 0 7 8 9 로 이루어진 행이 있을때

4번 인덱스에 5를 넣고 다음으로 가게 되었는데 5번 인덱스의 열에 이미 6이 존재하게 되면 check에서걸려서 아무것도 들어갈 수 있는 수가 없게 되므로 0을 리턴하고 빠져나오게됩니다

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

문제

문제

출처

ICPC

코드관련질문입니다.(참고자료)

ggggjin99 1년 전 0

munhwas1140 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말