1949 등산로 조성

#include <stdio.h>
#include <string.h>
#include <vector>
 
using namespace std;
 
int width, cut_max;
int rst_path;
int mountain[10][10];
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { -1, 1, 0, 0 };
int flag[10][10];
vector<pair<int, int> > summit;
 
void initialize();
void path(int y, int x, int depth);
 
int main() {
    int test;
    scanf("%d", &test);
 
    for (int t = 1; t <= test; t++) {
        initialize();
 
        for (int k = 1; k <= cut_max; k++) 
            for (int i = 1; i <= width; i++) 
                for (int j = 1; j <= width; j++) {
                    if (mountain[i][j] - k < 0)
                        continue;
            
                    mountain[i][j] -= k;
 
                    for (int h = 0; h < summit.size(); h++) {
                        int y = summit[h].first;
                        int x = summit[h].second;
                        
                        // flag 초기화
                        memset(flag, 0, sizeof(flag));
 
                        // 각각의 summit 기준 경로 찾기
                        flag[y][x] = 1;
                        path(y, x, 1);
                        flag[y][x] = 0;
                    }
 
                    mountain[i][j] += k;
                }
        
        printf("#%d %d\n", t, rst_path);
    }
}
 
void path(int y, int x, int depth) {
    int cnt = 0;
    for (int i = 0; i < 4; i++) {
        int xx = x + dx[i];
        int yy = y + dy[i];
 
        if (xx <= 0 || xx > width || yy <= 0 || yy > width)
            continue;
 
        int cur_height = mountain[y][x];
        int next_height = mountain[yy][xx];
        if (cur_height <= next_height)
            continue;
 
        if (flag[yy][xx] == 0) {
            flag[yy][xx] = 1;
            path(yy, xx, depth + 1);
            flag[yy][xx] = 0;
 
            cnt++;
        }
    }
 
    if (cnt == 0) {
        if (depth > rst_path) {
            rst_path = depth;
        }
    }
}
 
void initialize() {
    // scanf
    scanf("%d %d", &width, &cut_max);
 
    // rst_summit 초기화
    rst_path = 0;
 
    // num_summit
    int max_summit = -1;
    for (int i = 1; i <= width; i++) {
        for (int j = 1; j <= width; j++) {
            scanf("%d", &mountain[i][j]);
 
            if (max_summit < mountain[i][j]) {
                while (!summit.empty())
                    summit.pop_back();
 
                max_summit = mountain[i][j];
                summit.push_back(make_pair(i, j));
            }
            else if (max_summit == mountain[i][j]) {
                summit.push_back(make_pair(i, j));
            }
        }
    }
}
 

설마 이 방법으로 풀릴까 싶었는데 풀렸다..

시간복잡도가 엄청날 것 같아서 쫄려서 안풀고 있었는데..

댓글들 보니 내가 생각했던 방식 그대로 풀길래

나도 그냥 시도해봤다

코드 자체는 엄청 단순하다

걍 노가다 + DFS 방식 으로 처리를 했다

다행히 이제 DFS나 BFS 같은 방식의 문제는 엄청 수월하게 풀린다

시간복잡도에 대한 고민이나, 

적용이 조금 생소한 자료구조들에 대해서는 추가적인 공부가 필요할 것 같다