[소프트웨어 익스퍼트 아카데미][SWEA][모의 SW 역량테스트][ C++][1949번]등산로 조성

solution

가장 높은 봉우리를 찾아 그 장소를 시작점으로 dfs를 돌려 답을 확인하였습니다. 

*주의: K를 받아와서 등산로의 높이를 K만큼 줄일 수 있을 때 K만큼만 줄이는 것이 아닌 1부터 K 만큼 줄일 수 있도록 검사를 해주어야 합니다.

#include<iostream>
#include<memory.h>
#include<deque>
#include<queue>
using namespace std;
struct pos {
    int x;
    int y;
    int h;
};
 
int N, K, ans;
int mountain[9][9];
deque<pos> dq;
int p_x[4] = { 1,0,-1,0 };
int p_y[4] = { 0,1,0,-1 };
bool visited[9][9];
 
void find(int X, int Y, int hi, int cnt,int s) { //X,Y위치 ,h위치의 높이, 이동거리,s등산로를 한번 줄여줬나 안줄여줬나(s는 1로 시작하고 1이면 줄여준적이 없고 0이면 줄여준적이 있음)
    ans = max(ans, cnt);
    for (int dis = 0; dis < 4; dis++) {
        int ny = Y + p_y[dis];
        int nx = X + p_x[dis];
 
        if (ny > 0 && nx > 0 && ny < N + 1 && nx < N + 1&&!visited[ny][nx]) { //범위안이라면
            if (hi > mountain[ny][nx]) { //위치가 더 높다면
                visited[ny][nx]=true;
                find(nx, ny, mountain[ny][nx],cnt+1,s);
                visited[ny][nx] = false;
            }
            else {   // 더 낮다면
                if (s == 1) { // 한번도 등산로의 높이를 줄여준적이 없다면
                    for (int k = 1; k <= K; k++) {
                        if (hi > (mountain[ny][nx] - k)) {
                            visited[ny][nx] = true;
                            find(nx, ny, mountain[ny][nx] - k, cnt + 1, 0); //s를 0으로 만들어 더이상 등산로의 높이를 줄여주지 못하도록 함
                            visited[ny][nx] = false;
                        }
                    }
                }
            }
 
        }//범위안
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(false); cout.tie(false);
    int T;
    cin >> T;
    for (int t = 1; t <= T; t++) {
        N = 0; pos maxx; ans = 1; K = 0;
        while (!dq.empty())
            dq.pop_back();
        cin >> N;
        cin >> K;
        for (int Y = 1; Y <= N; Y++) {
            for (int X = 1; X <= N; X++) {
                cin >> mountain[Y][X];
                if (dq.empty()) {
                    maxx.x = X;
                    maxx.y = Y;
                    maxx.h = mountain[Y][X];
                    dq.push_back(maxx);
                }//if
                else {
                    if (mountain[Y][X] == dq.front().h) { //같으면 dq에 넣어주고
                        maxx.x = X;
                        maxx.y = Y;
                        maxx.h = mountain[Y][X];
                        dq.push_back(maxx);
                    }
                    else if (mountain[Y][X] > dq.front().h) { //더 크다면 다빼고 다시 넣어주기
                        while (!dq.empty())
                            dq.pop_front();
                        maxx.x = X;
                        maxx.y = Y;
                        maxx.h = mountain[Y][X];
                        dq.push_back(maxx);
                    }
                }//else
 
            }//for X
        }//for Y
        int endd = dq.size();
        for (int i = 0; i < endd; i++) {
            memset(visited, false, sizeof(visited));
            pos cur=dq.front();
            dq.pop_front();
            visited[cur.y][cur.x] = true;
            find(cur.x,cur.y,cur.h,1,1);
        }//for
        
        cout << "#" << t << " " << ans << endl;
    }//for T
}//main