1949. [모의 SW 역량테스트] 등산로 조성

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

고생 고생하면서 푼 문제 ... 

일단 BFS로 풀어보려고 시도 해보았다. 그런데 등산로를 깎는 경우에 대한 저장 정보 처리가 복잡해지기 떄문에 DFS로 바꾸어 풀었다..

문제의 제한 조건이 은근히 까다롭다

1. 제일 높은 등산로부터 등산로를 만들어야한다.

2. ★★ 최대 K 까지 깍을수 있으므로 꼭 K가 아닌 K보다 작은 수로 등산로를 깎을수도 있는 것 이 조건을 맞춰줘야 모든 테스트케이스에서 pass를 받을 수 있다.

3. visit 배열을 통해 다시 되돌아 가지 않도록 하자. 또 재귀가 풀릴때 방문을 해제하고, 길이도 줄여준다. 길이를 줄여주는것에 대한 생각을 못해서 오래걸렸다... 후..

코드

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<queue>
#include<vector>
#include<memory.h>
 using namespace std;
int T, N, K;
int map[8][8];
int visit[8][8];
int maxN;
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
int result;
struct point
{
    int x, y; 
};
vector<point> hn;
void check()
{
    hn.clear();
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (map[i][j] == maxN)
            {
                hn.push_back({ j,i});
            }
        }
    }
}
 
void dfs(int x, int y, int value, int leng, int cut)
{
    
    for (int i = 0; i < 4; i++)
    {
        int mx = x + dx[i];
        int my = y + dy[i];
        result = max(leng, result);
        if (mx <0 || mx > N - 1 || my < 0 || my >N - 1)
        {
            continue;
        }
        else
        {
            if (map[my][mx] <value && visit[my][mx]==0)
            {
                
                visit[my][mx] = 1;
                leng += 1;
                dfs(mx, my, map[my][mx],leng,cut);
                leng -= 1;
                visit[my][mx] = 0;
            }
            else if (map[my][mx] >= value && cut == 1 && visit[my][mx] ==0)
            {
                for (int offer = 1; offer <= K; offer++)
                {
                    if (map[my][mx] - offer < value)
                    {
                        visit[my][mx] = 1;
                        leng += 1;
                        dfs(mx, my, map[my][mx] - offer, leng, 0);
                        leng -= 1;
                        visit[my][mx] = 0;
                        break;
                    }
                }
                
            }
            
        }
        
    }
 
}
 
int main()
{
    freopen("sample_input.txt", "r", stdin);
    scanf("%d", &T);
    for (int test = 0; test < T; test++)
    {
        scanf("%d%d", &N, &K);
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                scanf("%d", &map[i][j]);
                maxN = max(maxN, map[i][j]);
            }
        }
        check();
        for (int i = 0; i < hn.size(); i++)
        {
            visit[hn[i].y][hn[i].x] = 1;
            dfs(hn[i].x, hn[i].y, maxN, 1,1);
            memset(visit, 0, sizeof(visit));
        }
        printf("#%d %d\n", test + 1, result);
        result = 0;
        maxN = 0;
        memset(map, 0, sizeof(map));
    }
    
}