이 문제는 몇가지 제한된 규칙을 가지고 있습니다. 정리하면 다음과 같습니다.
1) 등산로의 출발은 가장 높은 봉우리에서 시작한다.
2) 칸은 상하좌우로만 이동가능하며, 기존 봉우리보다 반드시 낮아야 한다.
3) 단 1칸을 최대 k 범위 내에서 깎을 수 있다. 1보다 작게도 깎을 수 있다(0까지)
문제를 풀 때는 항상 규칙을 먼저 확인해야 합니다. 일반적으로 문제를 풀 때 규칙은 문제를 쉽게 해주는 요소이기 때문입니다. 이 문제에서는 출발 지점이 제한되어 있고, 이동 지점이 제한 되어 있다는 점에서 문제가 쉬워지게 되는 것입니다.
3번 규칙, k 범위 이내에서 깎을 수 있다고 할 때, 만약 특정 칸을 깎는다면 얼마나 깎는 것이 유리할까요?
현재 봉우리의 높이가 h라고 한다면, 다음 칸으로 이동할 수 있는 봉우리의 높이 범위는 0 ~ h-1 입니다.
그리고 그 다음 봉우리에서 역시 또 다른 봉우리로 가려고 한다면, 그 봉우리보다는 낮은 봉우리로 이동해야 합니다.
즉, 이동할 가능성을 높이기 위해서는 가능한한 높은 봉우리로 이동하는 것이 유리하므로
깎아서 다른 곳으로 이동할 수 있는 경우엔 항상 h-1 높이를 만들어 이동하면 됩니다.
깊이 우선 탐색을 이용해 문제를 해결할 수 있으며, 반드시 방문한 지점을 체크하는 변수를 만들어야 합니다.
만약 체크하지 않는다면 아래와 같은 문제가 발생합니다.
7 | 6 |
4 | 2 |
k=2라고 가정해보겠습니다. (0,0) 에서 출발하여 (0,1)로 이동하였을 때, (0,0)의 방문 체크 여부를 하지 않는다면 (0,1)에서 (0,0) 으로 2만큼 깎아 다시 가게 되는 문제가 생깁니다. 그렇게 되면 원래 답인 3이 아닌, 5가 출력되는 문제가 발생합니다. 따라서 이런 점에 유의하셔야 합니다.
방문했던 지점의 체크와 해제는 아래 소스코드의 dfs 함수를 참고하세요.
※해당 소스코드는 참고용이며, 최적화 된 공식 솔루션 소스가 아닙니다. 이 소스를 그대로 복사하여 이용, 또는 제출하는 행위에 대한 불이익은 책임지지 않습니다.
#include<stdio.h>
using namespace std;
int n, k, b[8][8], ans;
int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };
bool visited[8][8];
void dfs(int x, int y, int h, int len, bool used)
{
if (ans < len) ans = len;
visited[x][y] = true;
for (int i = 0; i < 4; i++)
{
int nx = x + dir[i][0], ny = y + dir[i][1];
if (nx < 0 || ny < 0 || nx >= n || ny >= n || visited[nx][ny]) continue;
if (h > b[nx][ny])
dfs(nx, ny, b[nx][ny], len + 1, used);
else if (!used && h > b[nx][ny] - k)
dfs(nx, ny, b[x][y] - 1, len + 1, true);
}
visited[x][y] = false;
}
int main()
{
int T;
scanf("%d", &T);
for (int tc = 1; tc <= T; tc++)
{
int maxNum = 0;
scanf("%d %d", &n, &k);
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
scanf("%d", &b[i][j]);
if (b[i][j] > maxNum)
maxNum = b[i][j];
}
}
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (b[i][j] == maxNum)
dfs(i, j, b[i][j], 1, false);
printf("#%d %d\n", tc, ans);
ans = 0;
}
}