등산로 조성

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PoOKKAPIDFAUq&categoryId=AV5PoOKKAPIDFAUq&categoryType=CODE&problemTitle=%EB%93%B1%EC%82%B0%EB%A1%9C&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1&&&&&&&&& 

SW Expert Academy

'벽 부수고 이동하기'와 유사하다. 한 번만 팔 수 있으니까? bool을 써야겠다.

팠을 때 digged를 true로 만들고 digged가 true이면 이제 더 이상 건들일 수 없다.

 

'빙산' 문제를 떠올리면, 등산로 조성을 할 때 주어진 배열은 건들이면 안된다는 것을 배웠다.

이 문제도 마찬가지이다. 최대 높이가 여러 개 있으므로 배열은 건들이면 안된다.

 

이 문제는 최단거리의 문제가 아니다. 등산로의 최대 길이를 구하는 문제이다.

DFS를 써야함을 알 수 있다.

 

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int num, dig, result;
 
int arr[8][8];
bool check[8][8];
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
int dfs(int x, int y, int height, bool digged)
{
    check[x][y] = true;
    int cnt = 0;
    for (int k = 0; k < 4; k++)
    {
        int nx = x + dx[k];
        int ny = y + dy[k];
        if (nx >= 0 && ny >= 0 && nx < num && ny < num && !check[nx][ny])
        {
            if (arr[nx][ny] < height)
            {
                cnt = max(cnt, dfs(nx, ny, arr[nx][ny], digged));
            }
            else
            {
                //digged가 false이고 팠을 때 등산로 조성이 된다
                if (!digged && arr[nx][ny] - dig < height)
                {
                    cnt = max(cnt, dfs(nx, ny, height - 1, true));
                }
            }
        }
    }
 
    // 재귀가 끝날 때 방문했던 정점들을 다 false로 바꿔줘야한다!
    check[x][y] = false;
    // 재귀가 돌아오면서 cnt가 늘어간다.
    return cnt + 1;
}
 
 
int main()
{
    int test, maxi;
    cin >> test;
    for (int t = 1; t <= test; t++) 
    {
        cin >> num >> dig;
        result = 0;
        maxi = 0;
        for (int i = 0; i < num; i++)
        {
            for (int j = 0; j < num; j++)
            {
                cin >> arr[i][j];
                check[i][j] = false;
                maxi = max(maxi, arr[i][j]);
            }
        }
 
        for (int i = 0; i < num; i++) 
        {
            for (int j = 0; j < num; j++)
            {
                if (arr[i][j] == maxi)
                {
                    // digged는 false로 들어간다
                    int tmp = dfs(i, j, arr[i][j], false);
                    result = max(result, tmp);
                }
            }
        }
        cout << "#" << t << " " << result << '\n';
    }
 
    return 0;
}

cnt = max(cnt, dfs(nx, ny, height - 1, true));

이 부분이 가장 중요!

파야 하는 경우는 같거나 클 경우이다. 등산로는 내림차순에 최대가 되야하므로

깊게 파야할 이유가 없다! 

그러므로 height - 1을 넣는다.