[SWEA] 모의 SW 역량테스트 - 등산로 조성 (java)

문제 이해

 

문제보러가기

 

 

 

문제 이해부터 해보자.

핵심은 아래와 같다.

 

 

 

이렇게 갈 수 있는 거리의 최대값을 구해야 한다.!!!!

 

문제 이해를 하면 DFS + 백트레킹이 떠오를 것이다.

Why?

1.  모든 가능한 경로를 탐색하면서 가장 긴 경로를 찾는 유형의 문제 -> dfs

2. 각 경로에서의 최대 길이를 저장하고, 경로의 조건에 맞지 않는 경우 -> 백트래킹

 

 

해결방법 고안

 

K만 없으면 그냥 dfs 하면 되는데 k 때문에 고려해야 하는 상황이 있다;;

 

그래서 K를 아직 안쓴 경우와, K를 써버린 경우로 나누었다.

 

 

 

 

k가 없을 때 로직

// k가 없을 때
if (!flag) {
    // 자신보다 작으면 이동
    if (h > map[nx][ny]) {
        visited[nx][ny] = true;
        dfs(nx, ny, map[nx][ny], length + 1, flag);
        visited[nx][ny] = false;
    }
}

 

 

k가 있을 때 로직

 

수정 전

// k가 있을 때
else {
    // 자신보다 작으면 이동
    if (h > map[nx][ny]) {
        visited[nx][ny] = true;
        dfs(nx, ny, map[nx][ny], length + 1, flag);
        visited[nx][ny] = false;
    }
// 깎을 수 있는 경우
else if (h > map[nx][ny] - k) {
    int origin = map[nx][ny]; // 원래 높이를 저장
    for (int depth = 1; depth <= k; depth++) { // 1부터 k까지
        if (h > map[nx][ny] - depth) { // 현재 높이 h가 깎인 후의 높이보다 큰 경우
            map[nx][ny] -= depth; // 깊이만큼 깎아서 이동
            visited[nx][ny] = true;
            dfs(nx, ny, map[nx][ny], length + 1, false); // 깎아서 플래그 사용
            map[nx][ny] = origin; // 원래 높이로 복구
            visited[nx][ny] = false;
        }
    }
}

 

수정 후

// 깎을 수 있는 경우
else if (h > map[nx][ny] - k) {
    int origin = map[nx][ny]; // 원래 높이를 저장
    map[nx][ny] = h - 1; // 깎아서 이동
    visited[nx][ny] = true;
    dfs(nx, ny, map[nx][ny], length + 1, false); // 깎아서 플래그 사용
    map[nx][ny] = origin; // 원래 높이로 복구
    visited[nx][ny] = false;
}

 

 

 

 

 

코드보러가기