글 읽기 - 백트래킹으로 도전했는데 왜 답이 안나올까요?

wjavm2 4년 전 0

백트래킹으로 도전중인데 뭐가 문제일까요?? ans값이 안바뀌어요 ㅠㅠ

어떤 조건을 빠트렸는지 조언 부탁드립니다..!!!!

#include<iostream>

using namespace std;

int N, M, H;
int map[35][15] = { 0 };
int ans =999999;

bool available();
void DFS(int cnt,int x, int y);

int main()
{
	cin >> N >> M >> H;

	for (int i = 0; i < M; i++)
	{
		int a, b;
		cin >> a >> b;
		map[a][b] = 1;
	}

	DFS(0,1,1);
    if(ans < 4)   
	    cout << ans << endl;
    else
        cout<<-1<<endl;
	//system("pause");
	return 0;
}

bool available()
{
	int cc = 0;
	for (int i = 1; i <= N; i++)
	{
		int start = i;
		for (int j = 1; j <= H; j++)
		{
			if (map[j][i] == 1) start+=1;
			else if (i-1 > 1&& map[j][i - 1] == 1) start-=1;
		}
		if (start != i) return false;
		else cc++;
	}
	if (cc == N) return true;
	
}

void DFS(int cnt, int x, int y)
{
	
	if (available())
	{
		if (ans > cnt) ans = cnt;
		return;
	}
	
	//if (cnt == 3) return;
	
	for (int i = x; i <= H; i++)
	{
		for (int j = y; j <= N-1; j++)
		{
			if (j - 1 < 1 || j + 1 >= N)continue;
			
			if (map[i][j - 1] == 0 && map[i][j + 1] == 0 && map[i][j] == 0)
			{
				map[i][j] = 1;
				DFS(cnt + 1, i, j+1);
				map[i][j] = 0;
			}
		}
	}


}

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

문제

문제

출처

ICPC

백트래킹으로 도전했는데 왜 답이 안나올까요?

wjavm2 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말