[SWEA] 등산로 조성

[문제]

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PoOKKAPIDFAUq

SW Expert Academy

 

[풀이]

 

1) 가장 높은 봉우리가 시작점이다. 

2) 높은 지형에서 낮은 지형으로 가로 또는 세로 방향으로 연결이 되어야 한다.

3) 긴 등산로를 만들기 위해 딱 한 곳을 정해서 최대 K 깊이만큼 지형을 깎는 공사를 할 수 있다.

 

* 최대 K 라는 것을 알아야 한다. 꼭 K를 깎지 않아도 된다. 

 

* dfs 사용 (깊이 우선 탐색) 

 

* 시간 복잡도 O(n^2)

 

* 백트래킹 사용 

 

* flag를 사용해서 이미 깎은 후인지 아니면 깎기 전인지 구별해서 탐색을 진행한다. 

 

 

---

#include <iostream>
#include <vector>
using namespace std;
 
typedef long long ll;
 
int map[8][8];
int n, k;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
bool visited[8][8]; 
int ans = 0;
 
void dfs(int x, int y, int cnt, int prev, bool flag)
{
    visited[x][y] = true;
 
    if (cnt > ans)
    {
        ans = cnt;
    }
 
    for (int i = 0; i < 4; i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
 
        if (nx < 0 || nx >= n || ny < 0 || ny >= n || visited[nx][ny])
            continue;
 
        if (!flag)
        {
            //아직 깎지 않은 상태일 경우
            if (map[nx][ny] < map[x][y])
            {
                dfs(nx, ny, cnt + 1, map[nx][ny], flag);
            }
            else
            {
                if (map[nx][ny]-k < map[x][y])
                {
                    dfs(nx, ny, cnt + 1, map[x][y] - 1, true);
                    //'최대' K만큼 깎을 수 있다.=> K이하로도 깎을 수 있음을 고려해야한다.
                    //가장 높은 봉우리 높이 - 1을 prev로 설정한다.  
                    //깎은 후의 높이를 최대로 설정하면 안됨. 
                    //깎기 전의 높이를 최대로 설정해야 한다. 
                    //(높이를 계속 바꾸면 안된다.)
                }
            }
        }
        else {
            //깎은 상태의 경우 
            if (map[nx][ny] < prev)
                dfs(nx, ny, cnt+1, map[nx][ny], flag);
        }
    }
    visited[x][y] = false;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int t;
 
    cin >> t;
 
    for (int tc = 1; tc <= t; tc++)
    {
        cin >> n >> k; //자석 회전 횟수
        int max = 0, cnt = 0, tmp;
 
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                cin >> tmp;
                map[i][j] = tmp;
                if (max < map[i][j])
                {
                    max = map[i][j];
                }
            }
        }
 
        ans = 0;
 
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (map[i][j] == max)
                {
                    dfs(i, j, 1, map[i][j], false);
                }
            }
        }
        cout << "#" << tc << " " << ans << '\n';
    }
    return 0;
}