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