[C++]SW Expert Academy 등산로 조성

문제는 다음과 같다.

오늘은 SW Expert Academy 등산로 조성 문제를 풀어보도록 하자. 가장 높은 봉우리에서 시작해서 한 번 깎을 수 있고 최대 깎을 수 있는 높이는 K이다. 라는 조건을 보고 가장 효율적인 방법을 생각해보니

다음 봉우리가 현재의 봉우리보다 높고, 현재의 봉우리 -1 만큼의 봉우리가 될 수 있다면 방문처리를 해주고 그 만큼 깎고, 현재의 봉우리를 갱신한 후, 깎았다는 표시로 check = true표시를 해주고 dfs를 돌렸다.

만일 다음 봉우리가 현재의 봉우리보다 낮다면 방문처리를 해준 후 그냥 dfs를 돌렸다.

재귀에 대한 이해가 필요한 문제였다.

                                     [코드]
#include <iostream>
using namespace std;

int map[8][8];
int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };
bool visit[8][8];
int N, K, answer = 0;

void Init() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			map[i][j] = 0;
			visit[i][j] = false;
		}
	}
}

void Init_visit() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			visit[i][j] = false;
		}
	}
}

void dfs(int y, int x, int cur_height, int road, bool check) {
	if (answer < road) {//값 갱신
		answer = road;
	}

	for (int i = 0; i < 4; i++) {
		int my = y + dir[i][0];
		int mx = x + dir[i][1];

		if (my >= 0 && mx >= 0 && my < N && mx < N) {
			if (!visit[my][mx]) {
				if (map[my][mx] >= cur_height) { //다음 곳이 더 높고
					if (check) {//이미 깎았으면 돌아가셈
						continue;
					}
					if (map[my][mx] - cur_height + 1 <= K) { //최대 깎을 수 있는 범위 내에 있고 깎았을 때 현재보다 낮아지면
						visit[my][mx] = true;
						dfs(my, mx, cur_height - 1, road + 1, true);
						visit[my][mx] = false;
					}
				}
				else {//다음 곳이 낮다.
					visit[my][mx] = true;
					dfs(my, mx, map[my][mx], road + 1, check);
					visit[my][mx] = false;
				}
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int T, num = 0;
	cin >> T;

	while (T--) {
		int max_mountain = -987654321;
		answer = 0;
		cin >> N >> K;

		for (int i = 0; i < N; i++) {//Input the Map
			for (int j = 0; j < N; j++) {
				cin >> map[i][j];
				if (max_mountain < map[i][j]) {
					max_mountain = map[i][j];
				}
			}
		}

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] == max_mountain) {
					visit[i][j] = true;
					dfs(i, j, max_mountain, 1, false);
					Init_visit();
				}
			}
		}
		cout << '#' << ++num << ' ' << answer << '\n';
		Init();//Initialize
	}
}