[SWEA] 1949 등산로 조성

1949 등산로 조성

풀이)

dfs를 이용해서 가능한 모든 경우를 다 살펴본 문제이다.

과정은 이러하다.

1. 가장 지형이 높은 곳들의 위치를 저장해 둔다.

2. 각 높은 곳들의 위치에서 dfs를 통해 등산로 길이를 구한다.

3. 그 중 최고의 등산로 길이를 출력한다.

dfs함수를 자세히 설명하면

1) 현재 좌표값에서 상하좌우로 움직였을때 지도 범위내에 들어오는 지 확인

2) 범위내에 들어온다면 이전에 지형을 깎아본 적이 있는 지 확인

 2.1) 지형을 이미 깎아봤다면

다음에 움직일 곳의 지형의 높이 확인

현재 지형의 높이보다 작다면 → 이동

작지 않다면 →이동 그만하고 지금까지의 등산로 길이 체크

 2.2) 지형을 아직 깎아보지 않았다면

다음에 움직일 곳의 지형의 높이를 확인

현재 지형의 높이보다 작다면 → 이동

작지 않다면 → (현재 지형 높이 - 1) 높이로 깎을 수 있는지 확인

→깎을 수 있다면 깎고 이동.

→없다면 이동 그만하고 지금까지의 등산로 길이 체크

(왜 (현재지형 높이 - 1) 높이로 깎아야하는지?

최대한 덜 깎아놔야 다음번 그 지형에서 이동할 때 다음칸으로 이동할 가능성이 높기 때문이다.

현재 있는 곳보다 낮은 지형이기만 하면 이동이 가능하니깐 최대한 높은 지형으로 남겨나야 함.)

코드를 보면 더 이해가 쉬울 수도 있다.

코드)

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <string.h>
using namespace std;
 
int n, k;
int map[8][8];
int MAX;
vector <pair<int, int>> high;
bool visited[8][8];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
int result;
 
//check =1 이면 이전에 깎았다는 뜻
void dfs(int y, int x,bool check,int depth) {
    for (int i = 0; i < 4; i++) {
        int ny = y + dy[i];
        int nx = x + dx[i];
        if (ny >= 0 && ny < n&&nx >= 0 && nx < n) {
            if (visited[ny][nx]) continue;
            
            if (check) { //이미 이전에 지형을 한 번 깎은 경우
                if (map[ny][nx] < map[y][x]) { //다음에 움직일 지형의 높이가 현재 지형의 높이보다 작다면 이동가능
                    visited[ny][nx] = true;
                    dfs(ny, nx, check, depth + 1);
                    visited[ny][nx] = false;
                }
            }
            else { //아직 안깎은 경우
                if (map[ny][nx] >= map[y][x]) {//가야할 곳이 현재있는곳보다 같거나 높은곳이라면 ->이동불가, 깍아야함
                    //현지높이보다 1만큼만 작게 깎음, 많이 깎는다고 좋은거 아님
                    if (map[ny][nx] - (map[y][x] - 1) <= k) {//깍아야할 깊이 k이하라면 깍을 수 있음
                        int temp = map[ny][nx];
                        map[ny][nx] = (map[y][x]-1); 
                        visited[ny][nx] = true;
                        dfs(ny, nx, 1, depth + 1);
                        visited[ny][nx] = false;
                        map[ny][nx] = temp; //원래값으로 돌려놓기
                    }
                }
                else {
                    visited[ny][nx] = true;
                    dfs(ny, nx, check, depth + 1);
                    visited[ny][nx] = false;
                }
            }
        }
    
    }
    result = max(result, depth);
}
 
int main() {
    //freopen("sample_input.txt", "r", stdin);
    int T = 0;
    scanf("%d", &T);
    for (int test_case = 1; test_case <= T; test_case++) {
        scanf("%d %d", &n, &k);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                scanf("%d", &map[i][j]);
                if (MAX < map[i][j]) {
                    high.clear();
                    MAX = map[i][j];
                    high.push_back({ i,j });
                }
                else if(MAX == map[i][j]) {
                    high.push_back({ i,j });
                }
            }
        }
 
        for (int i = 0; i < high.size(); i++) {
            visited[high[i].first][high[i].second] = true;
            dfs(high[i].first, high[i].second, 0, 1);
            memset(visited, false, sizeof(visited));
        }
 
        printf("#%d %d\n", test_case, result);
        high.clear();
        MAX = 0;
        result = 0;
    }
    return 0;
}