[코드트리] 디버깅

문제링크 : https://www.codetree.ai/training-field/frequent-problems/problems/debugging/description?page=1&pageSize=20

💻 문제 풀이 : C++

#include <iostream>
#include <cstring>

using namespace std;

struct Data
{
	int a, b;
};

int n, m, h;
int map[35][35];
int tmpMap[35][35];

int dr[] = { 0, 0 };
int dc[] = { -1, 1 };

void CLEAR()
{
	n = m = h = 0;
	memset(map, 0, sizeof(map));
	memset(tmpMap, 0, sizeof(tmpMap));

}

void INPUT()
{
	cin >> n >> m >> h;
	for (int i = 0; i < m; i++)
	{
		int a, b;
		cin >> a >> b;
		// map 만들기
		map[a-1][b-1] = 1;
		// map[a][b+1] = 1;
	}

	// (1-2), (3-2), (5-1)
	// Okay 확인 어떻게??
	// 1 ~ n 까지 확인
	// 1을 만나면 좌우 체크
	// 계속 내려감
	// h까지 내려가면 현재 열 return
	// return이 자기자신인경우 (okay)??
}

void copyMap()
{
	for (int i = 0; i <= n; i++)
	{
		for (int j = 0; j <= h; j++)
		{
			tmpMap[j][i] = map[j][i];

		}
	}
}

int isBugClear()
{
	for (int i = 0; i < n - 1; i++)
	{
		int start = i;
		for (int j = 0; j < h; j++)
		{
			if (tmpMap[j][start] == 1)
			{
				start += 1;
			}
			else if (start - 1 >= 0 && tmpMap[j][start -1] == 1)
			{
				start -= 1;
			}
		}
		if (start != i) return 0;
	}
	return 1;
}

int isLineOkay(int nowRow, int nowCol)
{
	for (int dir = 0; dir < 2; dir++)
	{
		int r = nowRow + dr[dir];
		int c = nowCol + dc[dir];
		if (r < 0 || c < 0 || r> n || c > h) continue;
		if (tmpMap[r][c] == 1 || map[r][c]) {
			return 0;
		}
	}
	return 1;
}

void dfs(int depth, int addline, int start, int &ans)
{
	if (depth == addline)
	{
		// int debug = 0;
		if (isBugClear()) {
			ans = addline;
		}
		return;
	}

	for (int i = start; i <= (n - 1) * h; i++)
	{
		int r = i / (n - 1);
		int c = i % (n - 1);
		if (r < 0 || c < 0 || r > n || c > h) continue;
		if (tmpMap[r][c] == 1) continue;
		if (!isLineOkay(r, c)) continue;
		tmpMap[r][c] = 1;
		dfs(depth + 1, addline, i + 1, ans);
		tmpMap[r][c] = 0;
	}
}

void SOLVE()
{
	int answer = 2134567890;

	// 선 최대 (n-1 X h) 개 중 1~3개 조합
	for (int i = 0; i <= 3; i++)
	{
		copyMap();
		dfs(0, i, 0, answer);
		if (answer != 2134567890) {
			cout << answer << endl;
			return;
		}
	}

	cout << -1 << endl;
	return;
}

int main()
{
	CLEAR();
	INPUT();
	SOLVE();

	return 0;
}

📌 memo 😊