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

shinsh1932 4년 전 0

반례를 찾을 수가 없네요...

예제 + 다른 스도쿠도 입력으로 넣어봤는데 답이 잘나옵니다..

코드도 허접하고, 주석은 더 허술합니다.

죄송합니다ㅜㅜ

반례 좀 부탁드리겠습니다ㅠㅠ

#include<iostream>

using namespace std;

#define MAX	9

int N; 
bool check = true;
bool row_visited[MAX];
bool col_visited[MAX];
bool sqr_visited[MAX];

int table[MAX][MAX];
int x_point[MAX * MAX];
int y_point[MAX * MAX];

void DFS(int cnt);

int main()
{
	///
	for (int i = 0; i < MAX; i++)
	{
		for (int j = 0; j < MAX; j++)
		{
			scanf("%d", &table[i][j]);
			if (table[i][j] == 0)
			{
                // 값이 0 인 지점의 위치 저장
				x_point[N] = i;
				y_point[N] = j;
				N++;				
			}				
		}
	}

	DFS(0);

	return 0;
}

void DFS(int cnt)
{
	if (cnt == N)
	{
		for (int i = 0; i < MAX; i++)
		{
			for (int j = 0; j < MAX; j++)
				printf("%d ", table[i][j]);
			printf("\n");
		}			
        
        //탈출용
		check = false;
		return;
	}
    
    //새로운 포인트에서 갈 수 있는 경로
	for (int p = 0; p < MAX; p++)
	{
		row_visited[p] = false;
		col_visited[p] = false;
		sqr_visited[p] = false;
	}

	for (int p = 0; p < MAX; p++)
	{
		if (table[x_point[cnt]][p] != 0)
			row_visited[table[x_point[cnt]][p] - 1] = true;

		if (table[p][y_point[cnt]] != 0)
			col_visited[table[p][y_point[cnt]] - 1] = true;
	}

	for (int p = 0; p < MAX / 3; p++)
	{
		for (int q = 0; q < MAX / 3; q++)
		{
			if (table[x_point[cnt] / 3 * 3 + p][y_point[cnt] / 3 * 3 + q] != 0)
				sqr_visited[table[x_point[cnt] / 3 * 3 + p][y_point[cnt] / 3 * 3 + q] - 1] = true;
		}
	}

	for (int i = 0; i < MAX; i++)
	{
		//
		if (row_visited[i] == false && col_visited[i] == false && sqr_visited[i] == false)
		{
			table[x_point[cnt]][y_point[cnt]] = i + 1;

			DFS(cnt + 1);

			if (!check)
				break;

			table[x_point[cnt]][y_point[cnt]] = 0;

		}				
	}	
}

djm03178 4년 전 1

반례를 찾지는 않았지만 매우 의심스러운 부분은 재귀함수가 visited 배열을 공유하고 있다는 점이네요. 같은 호출 내에서 추가로 재귀호출을 하기 이전과 이후의 배열의 상태가 완전히 달라질 텐데 안 괜찮을 것 같습니다.

shinsh1932 4년 전 0

답변 감사드립니다! 확인해 보도록 하겠습니다ㅎㅎ

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

문제

문제

출처

ICPC

반례.. 부탁드립니다ㅠㅠ

shinsh1932 4년 전 0

djm03178 4년 전 1

shinsh1932 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말