static int N, K;
static int board[8][8];
static int start[5][2]; //최고봉 위치는 최대 5개,
static int d[4][2] = {
-1, 0, //up
1, 0, //down
0, -1, //left
0, 1 //right
};
static int visit[8][8];
static int max_len;
static inline bool out_of_bound(int y, int x)
{
if (y < 0 || y >= N)
return true;
if (x < 0 || x >= N)
return true;
return false;
}
static void __solution(int y, int x, int len, int is_cut)
{
if (len > max_len)
max_len = len;
visit[y][x] = true; //핵심
for (int i = 0; i < 4; i++) //가로, 세로로 움직임,
{
int ny = y + d[i][0];
int nx = x + d[i][1];
if (out_of_bound(ny, nx))
continue;
if (visit[ny][nx]) /*놓쳤던 부분*/
continue;
if (board[ny][nx] >= board[y][x])
{
if (is_cut) //더 이상 자를 수 없음,
continue;
if (board[ny][nx] == board[y][x])
{
board[ny][nx] -= 1; //key
__solution(ny, nx, len + 1, 1);
board[ny][nx] += 1; //key
}
else if (board[ny][nx] > board[y][x])
{
int diff = board[ny][nx] - board[y][x];
if (!(K >= diff + 1)) /*핵심*/
continue;
diff += 1;
board[ny][nx] -= diff; //key
__solution(ny, nx, len + 1, 1);
board[ny][nx] += diff; //key
}
}
else
__solution(ny, nx, len + 1, is_cut);
}
visit[y][x] = false; //핵심
}
static int solution(void)
{
int max = 0, cnt = 0;
scanf("%d %d", &N, &K);
for (int y = 0; y < N; y++)
{
for (int x = 0; x < N; x++)
{
scanf("%d", &board[y][x]);
if (board[y][x] > max)
{
max = board[y][x];
cnt = 0;
}
if (board[y][x] == max)
{
start[cnt][0] = y;
start[cnt++][1] = x;
}
}
}
max_len = 0;
for (int i = 0; i < cnt; i++)
__solution(start[i][0], start[i][1], 1, 0);
return max_len;
}기본적으로 전체를 전부 탐색하도록 하였다.
solution()에서는 입력 및 높이가 제일 높은 위치를 찾아 start배열에 저장한다.
그 후, 모든 위치에 대해서 해당 지점 부터 시작했을 시 최대로 얼마나 뻗어 갈 수 있는지 확인한다.
그래서 __solution()의 구현이 핵심이라 할 수 있다.
먼저 __solution()은 재귀로 구현되어 있다.
왜냐하면 현재 위치에서 4방향으로 모두 가봐야 하기 때문이다.
(최대, 최소를 구하는 문제에서는 가급적 전체를 전부 탐색해보는 것이 정확하다.)
또, 움직인 위치에서 4방향 모두 가봐야 하기 때문에, 재귀로 코드를 작성하는 것이 훨씬 수월하다.
그리고 여기서 중요한 점이 visit에 대한 정보이다.
그 동안 시뮬레이션 문제등을 많이 풀어와서 이 부분을 잠시 생각하지 않고 있었다.
다음은 이동할 위치의 높이가 현재 위치보다 낮은 경우이다.
이 경우는 그냥 재귀를 계속 진행하면 된다.
문제는 이동할 위치의 높이가 현재 위치와 같거나 더 높은 경우이다.
여기서 중요한 점은 현재 이동한 경로에서 추가적인 공사가 있었는지의 여부이다.
이 정보는 is_cut이라는 변수가 담당하는데, 값이 0이면 공사를 안한경우, 1이면 한 경우이다.
그래서 위 경우에서 이미 공사를 한 경우라면 더 나아갈 수 없다.
그래서 더 나아가지 못한다.
공사를 안한경우라면 좀 따져봐야 한다.
이동할 위치의 높이가 현재 높이와 같은 경우 1만 빼주면 된다.
그 이유는 당연하게도 높이차가 최대한 작아야지 등산로를 더 만들 수 있기 때문이다.
9 -> 9 일 때 9를 1로 만들면 최대 1의 길이가 더 추가될 뿐이지만,
9를 8로 만들면 최대 8의 길이를 더 추가할 수 있기 때문이다.
이번에는 이동할 위치의 높이가 현재 높이보다 더 큰 경우이다.
이 경우는 앞서 언급한 것처럼 이동할 위치를 현재 높이 - 1 로 만 만들어 주면 된다.
그런데 여기서 중요한 것이 그 만큼 깎을 수 있냐는 것이다.
공사를 할 수 있는 깊이 K가 입력으로 주어지는데,
이 값이 5라 하고,
2 -> 9 로 간다하면 공사를 위해 필요한 최소값은 7 + 1, 즉 {(현재 높이 - 다음 높이) + 1} 이다.
그래서 K가 이 값보다 작다면 더 진행 할 수 없고,
반대로 K가 이 값 이상이면 더 진행 할 수 있는 것이다.
마지막은 //핵심 또는 //key라고 적은 부분에 대한 것이다.
과거 벽돌 깨기라는 문제에서 재귀로 인해 바뀐 부분을 복구하기 위해 현재 시점의 정보를 복사해서 다음 재귀문에서 이를 복사하여 사용하는 방식으로 구현했던 기억이 있다.
물론 좀 푼지 좀 오래된 문제라 어떠한 이유에서 이와 같이 코드를 작성했는지 기억은 안나지만,
위 코드를 처음 작성하기 전에 비슷한 방식으로 구현할 까 생각했었다.
그러나 재귀를 하기전에 값을 변경했으면, 재귀 후에는 해당 값을 원상 복구 시키는 것이 당연하다는 생각을 하여
원래 생각했던 방식대로 코드를 작성하지 않았다.
visit 역시 같은 개념이다. 함수가 실행되었다는 것은 현재 위치가 적합한 경로에 있다는 것을 의미하기 때문에,
반복문 시작전에 방문을 하고 반복문 후 함수가 종료되기 전에 방문한 기록을 삭제하는 것이다.
