[SWEA] 1949. 등산로 조성

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
using namespace std;

int T, N, K, rst, cut_v;
int map[8][8];
int is_visit[8][8];
vector <pair<int, int>> v;
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

void input() {
	cin >> N >> K;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			cin >> map[i][j];
	rst = 0;
	while (v.size()) {
		v.pop_back();
	}
}

void find_start_point() {
	int num = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			num = max(num, map[i][j]);
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (num == map[i][j]) {
				v.push_back(make_pair(i, j));
			}
		}
	}
}

int is_range(int x, int y) {
	if (x >= 0 && x < N && y >= 0 && y < N) return true;
	return false;
}

void dfs(int x, int y, int cnt, int cut) {
	is_visit[x][y] = 1;
	rst = max(rst, cnt);

	int nx, ny;
	for (int i = 0; i < 4; i++) {
		nx = x + dx[i];
		ny = y + dy[i];	
		if (!is_range(nx, ny) || is_visit[nx][ny]) continue;
		if (map[x][y] <= map[nx][ny]) {
			if (cut == 0) continue; 
			cut_v = abs(map[nx][ny] - map[x][y]) + 1;
			if (K >= cut_v) {
				map[nx][ny] = map[nx][ny] - cut_v;
				dfs(nx, ny, cnt + 1, !cut);
				map[nx][ny] += cut_v;
			}
		}
		else {
			dfs(nx, ny, cnt + 1, cut);
		}
	}
	is_visit[x][y] = 0;
}

void solve() {
	find_start_point();
	for (int i = 0; i < v.size(); i++) {
		dfs(v[i].first, v[i].second, 1, 1);
	}
}

int main() {
	cin >> T;
	for (int tc = 1; tc <= T; tc++) {
		input();
		solve();
		cout << "#" << tc << " " << rst << endl;
	}
}

1. nx, ny를 전역변수로 두었다가 dfs가 끝날 시점에 map 복귀가 정상적으로 되지 않아 디버깅을 엄청 했다. 무작정 변수를 전역에 두지 않기로 주의하자!
2. 문제의 핵심은 '최소한'으로 언덕을 깎는 것이다.