1949. [모의 SW 역량테스트] 등산로 조성

정말 많이틀렸다.. 틀린이유는 딱한가지였는데... BFS할땐 기똥차게잘하면서 왜 맨날 DFS나 백트래킹할때는

시작포인트를 체킹안하는질모르겠다..

 

#include<iostream>
#include<cstring>
#include<cstdlib>

using namespace std;

int tc,n,m;
int map[10][10];
bool d[10][10];
int ans = 0;
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
bool check(int x, int y, int cnt) {
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i]; int ny = y + dy[i];
		if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
			if (d[nx][ny] == false) {
				if (map[nx][ny] < map[x][y]) return true;
				else {
					if (cnt < 1) {
						for (int j = 1; j <= m; j++) {
							int temp = map[nx][ny];
							temp -= j;
							if (temp < map[x][y]) return true;
						}
					}
				}
			}
		}
	}
	return false;
}

void dfs(int len, int x, int y, int cnt) {
	if (!check(x, y, cnt)) {
		if (len > ans) ans = len;
		d[x][y] = false;
		return;
	}
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i]; int ny = y + dy[i];
		if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
			if (d[nx][ny] == false) {
				if (map[nx][ny] < map[x][y]) {
					d[nx][ny] = true;
					dfs(len+1, nx, ny, cnt);
					d[nx][ny] = false;
				}
				if (cnt < 1) {
					for (int j = 1; j <= m; j++) {
						map[nx][ny] -= j;
						if (map[nx][ny] < map[x][y]) {
							d[nx][ny] = true;
							dfs(len + 1, nx, ny, cnt + 1);
							d[nx][ny] = false;
						}
						map[nx][ny] += j;
						
					}
				}
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> tc;
	for (int t = 1; t <= tc; t++) {
		cin >> n >> m;
		int max = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				cin >> map[i][j];
				if (map[i][j] > max) max = map[i][j];
			}
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (map[i][j] == max) {
                    d[i][j] = true;
					dfs(1, i, j, 0);
                    d[i][j] = false;
					memset(d, false, sizeof(d));
				}
			}
		}
		
		cout <<"#"<<t<<' '<<ans << '\n';
		ans = 0;
		
	}
	return 0;
}

 

main()에서 dfs하는과정에서, 시작 d[i][j] 를 체킹하지않아서 자꾸 테스트케이스 4개가틀렸다.. 진짜 몇번을 바꾼질모르겠네...