글 읽기 - 55%에서 틀립니다. 놓친 부분과 따로 궁금한 점 질문드립니다.

rnjstpgns91 4년 전 1

1. 55%까진 통과하는데 어떤 케이스에서 오답이 나오는지 궁금합니다.
기존에 작성한 코드는 그냥 85번 line과 같은 색종이 사용이 5장 이하인 경우에만 DFS 작동하도록 따로 조건문을 걸어주지 않았습니다(87~89번만 존재했었음, 다른 size의 색종이에 대해서도 마찬가지). 그 이유는 60번 line에 DFS에 들어왔을 때 사용한 색종이가 5장이 초과된 경우에 바로 return해주기 때문에 따로 조건문을 안썼습니다. 근데 이렇게 하면 테스트케이스는 모두 통과하여도 제출시 바로 틀렸다는 결과가 나오는데 어떤 차이가 있는 것인가요?

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

#define endl "\n"


int Array[10][10];
int my_visit[10][10];
int cnt = 0, cnt2 = 0, cnt3 = 0, cnt4 = 0, cnt5 = 0, total_cnt = 0;
int ans = 999999;

struct point
{
	int x;
	int y;
};

vector<point> v;

void input()
{
	for (int i = 0; i < 10; i++)
		for (int j = 0; j < 10; j++)
		{
			cin >> Array[i][j];
			if (Array[i][j] == 1)
			{
				v.push_back({ j,i });
				total_cnt++;
			}
		}
}

int check(int y, int x, int c)
{
	int flag = 1; //c x c 범위가 모두 1이면 1 return
	for (int i = y; i < y + c; i++)
	{
		for (int j = x; j < x + c; j++)
		{
			if (Array[i][j] == 0 || my_visit[i][j] == true) return 0; //방문했으면 못가므로 return 0
		}
	}

	return flag;
}

void visit(int y, int x, int c, int tf)
{
	for (int i = y; i < y + c; i++)
		for (int j = x; j < x + c; j++)
			my_visit[i][j] = tf;
}

void DFS(int idx, int C, int C2, int C3, int C4, int C5, int count)
{
	if (C > 5 || C2 > 5 || C3 > 5 || C4 > 5 || C5 > 5) return;

	if (C + C2 + C3 + C4 + C5 > ans) return;

	if (count == total_cnt)
	{
		ans = min(ans, C + C2 + C3 + C4 + C5);
		return;
	}

	if (my_visit[v[idx].y][v[idx].x] == true)
	{
		DFS(idx + 1, C, C2, C3, C4, C5, count);
		return;
	}

	int c1 = check(v[idx].y, v[idx].x, 1);
	int c2 = check(v[idx].y, v[idx].x, 2);
	int c3 = check(v[idx].y, v[idx].x, 3);
	int c4 = check(v[idx].y, v[idx].x, 4);
	int c5 = check(v[idx].y, v[idx].x, 5);

	//큰거 하면 나머지 모두 포함이므로 반복되는 조건문들 거를 수 있음. 2부터하면 2하고 else if 3에서 또 2에 대한 작업하므로
	if (c5 == 1)
	{
		if (C5 + 1 <= 5)
		{
			visit(v[idx].y, v[idx].x, 5, true); // 5x5 범위만큼 0으로 바꿔주기 
			DFS(idx + 1, C, C2, C3, C4, C5 + 1, count + 25);
			visit(v[idx].y, v[idx].x, 5, false); // 5x5 범위만큼 원상 복구 해주기 (백트래킹)
		}

		if (C4 + 1 <= 5)
		{
			visit(v[idx].y, v[idx].x, 4, true);
			DFS(idx + 1, C, C2, C3, C4 + 1, C5, count + 16);
			visit(v[idx].y, v[idx].x, 4, false);
		}

		if (C3 + 1 <= 5)
		{
			visit(v[idx].y, v[idx].x, 3, true);
			DFS(idx + 1, C, C2, C3 + 1, C4, C5, count + 9);
			visit(v[idx].y, v[idx].x, 3, false);
		}

		if (C2 + 1 <= 5)
		{
			visit(v[idx].y, v[idx].x, 2, true);
			DFS(idx + 1, C, C2 + 1, C3, C4, C5, count + 4);
			visit(v[idx].y, v[idx].x, 2, false);
		}

		if (C + 1 <= 5)
		{
			visit(v[idx].y, v[idx].x, 1, true);
			DFS(idx + 1, C + 1, C2, C3, C4, C5, count + 1);
			visit(v[idx].y, v[idx].x, 1, false);
		}
	}
	else if (c4 == 1)
	{
		if (C4 + 1 <= 5)
		{
			visit(v[idx].y, v[idx].x, 4, true);
			DFS(idx + 1, C, C2, C3, C4 + 1, C5, count + 16);
			visit(v[idx].y, v[idx].x, 4, false);
		}

		if (C3 + 1 <= 5)
		{
			visit(v[idx].y, v[idx].x, 3, true);
			DFS(idx + 1, C, C2, C3 + 1, C4, C5, count + 9);
			visit(v[idx].y, v[idx].x, 3, false);
		}

		if (C2 + 1 <= 5)
		{
			visit(v[idx].y, v[idx].x, 2, true);
			DFS(idx + 1, C, C2 + 1, C3, C4, C5, count + 4);
			visit(v[idx].y, v[idx].x, 2, false);
		}

		if (C + 1 <= 5)
		{
			visit(v[idx].y, v[idx].x, 1, true);
			DFS(idx + 1, C + 1, C2, C3, C4, C5, count + 1);
			visit(v[idx].y, v[idx].x, 1, false);
		}
	}
	else if (c3 == 1)
	{
		if (C3 + 1 <= 5)
		{
			visit(v[idx].y, v[idx].x, 3, true);
			DFS(idx + 1, C, C2, C3 + 1, C4, C5, count + 9);
			visit(v[idx].y, v[idx].x, 3, false);
		}

		if (C2 + 1 <= 5)
		{
			visit(v[idx].y, v[idx].x, 2, true);
			DFS(idx + 1, C, C2 + 1, C3, C4, C5, count + 4);
			visit(v[idx].y, v[idx].x, 2, false);
		}

		if (C + 1 <= 5)
		{
			visit(v[idx].y, v[idx].x, 1, true);
			DFS(idx + 1, C + 1, C2, C3, C4, C5, count + 1);
			visit(v[idx].y, v[idx].x, 1, false);
		}
	}

	else if (c2 == 1)
	{
		if (C2 + 1 <= 5)
		{
			visit(v[idx].y, v[idx].x, 2, true);
			DFS(idx + 1, C, C2 + 1, C3, C4, C5, count + 4);
			visit(v[idx].y, v[idx].x, 2, false);
		}

		if (C + 1 <= 5)
		{
			visit(v[idx].y, v[idx].x, 1, true);
			DFS(idx + 1, C + 1, C2, C3, C4, C5, count + 1);
			visit(v[idx].y, v[idx].x, 1, false);
		}
	}
	else if(c1 == 1)
	{
		if (C + 1 <= 5)
		{
			visit(v[idx].y, v[idx].x, 1, true);
			DFS(idx + 1, C + 1, C2, C3, C4, C5, count + 1);
			visit(v[idx].y, v[idx].x, 1, false);
		}
	}

	else return;

}

void solve()
{
	DFS(0, 0, 0, 0, 0, 0, 0);

	if (ans == 999999) cout << "-1" << endl;
	else cout << ans << endl;
}

int main()
{
	input();

	solve();

	return 0;
}