[SWEA] #1949 _ 등산로 조성

[등산로 조성] https://swexpertacademy.com/main/code/problem/problemDetail.do

SW Expert Academy

top이라는 벡터에 제일 높은 봉우리의 좌표를 넣어둔다.

top에 있는 좌표에서 시작하여 solve 함수에서 dfs를 이용하여 최대 길이를 구한다.

 

한 번 깎은 곳의 좌표는 cut 벡터에 저장하고,

cut 벡터의 사이즈가 0일 경우에는 한 번도 깎지 않은 것으로 간주하여

깎아 갈 수 있는 최대 길이를 갱신하도록 구현하였다.

 

[ 소스 코드 ]

#include <cstdio>
#include <vector>
#include <algorithm>
#define MAX 8

using namespace std;

int dx[] = { 0, 0, -1, 1 }, dy[] = { -1, 1, 0, 0 };
int N, K, long_path, cut_depth;
int map[MAX][MAX], chk[MAX][MAX];
vector<pair<int, int> >top, cut;

void solve(int val, int y, int x);
void initChk();
int main() {
	int T;

	scanf("%d", &T);
	for (int i = 1; i <= T; i++) {
		scanf("%d %d", &N, &K);
		for (int j = 0; j < N; j++) {
			for (int k = 0; k < N; k++) {
				scanf("%d", &map[j][k]);

				if (top.size() > 0) { // setting top
					if (map[top.front().first][top.front().second] < map[j][k]) {
						top.clear();
						top.push_back(make_pair(j, k));
					}
					else if (map[top.front().first][top.front().second] == map[j][k]) top.push_back(make_pair(j, k));
				}
				else top.push_back(make_pair(j, k));
			}
		}
		long_path = 0;

		for (int j = 0; j < top.size(); j++) {
			solve(1, top[j].first, top[j].second);
			initChk();
		}

		printf("#%d %d\n", i, long_path);
		top.clear();
	}

	return 0;
}

void initChk() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) chk[i][j] = 0;
	}
}

void solve(int val, int y, int x) {
	int tmp_y, tmp_x;
	chk[y][x] = 1;
	long_path = max(long_path, val);
	
	for (int i = 0; i < 4; i++) {
		tmp_x = x + dx[i];
		tmp_y = y + dy[i];

		if (tmp_x < 0 || tmp_y < 0 || tmp_x >= N || tmp_y >= N) continue;
		if (chk[tmp_y][tmp_x]) continue;
		if (map[tmp_y][tmp_x] >= map[y][x]) {
			if (cut.size()) continue;
			else {
				if (map[tmp_y][tmp_x] - K >= map[y][x]) continue;
				else {
					cut.push_back(make_pair(tmp_y, tmp_x));
					cut_depth = map[tmp_y][tmp_x] - map[y][x] + 1;
					map[tmp_y][tmp_x] -= cut_depth;
				}
			}
		}

		solve(val + 1, tmp_y, tmp_x);

		if (cut.size()) {
			if (cut.front().first == tmp_y && cut.front().second == tmp_x) {
				map[tmp_y][tmp_x] += cut_depth;
				cut.pop_back();
			}
		}
	}
	chk[y][x] = 0;
}