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

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

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

• 시간 : 50개 테스트케이스를 합쳐서 C의 경우 3초 / C++의 경우 3초 / Java의 경우 3초 / Python의 경우 15초
• 메모리 : 힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.


등산로를 조성하려고 한다.

등산로를 만들기 위한 부지는 N * N 크기를 가지고 있으며, 이곳에 최대한 긴 등산로를 만들 계획이다.

등산로 부지는 아래 [Fig. 1]과 같이 숫자가 표시된 지도로 주어지며, 각 숫자는 지형의 높이를 나타낸다.
 

 

등산로를 만드는 규칙은 다음과 같다.

   ① 등산로는 가장 높은 봉우리에서 시작해야 한다.

   ② 등산로는 산으로 올라갈 수 있도록 반드시 높은 지형에서 낮은 지형으로 가로 또는 세로 방향으로 연결이 되어야 한다.
       즉, 높이가 같은 곳 혹은 낮은 지형이나, 대각선 방향의 연결은 불가능하다.

   ③ 긴 등산로를 만들기 위해 딱 한 곳을 정해서 최대 K 깊이만큼 지형을 깎는 공사를 할 수 있다.

N * N 크기의 지도가 주어지고, 최대 공사 가능 깊이 K가 주어진다.

이때 만들 수 있는 가장 긴 등산로를 찾아 그 길이를 출력하는 프로그램을 작성하라.


[예시]

위 [Fig. 1]과 같이 N = 5인 지도가 주어진 경우를 살펴보자.

가장 높은 봉우리는 높이가 9로 표시된 세 군데이다.

이 세 곳에서 출발하는 가장 긴 등산로 중 하나는 아래 [Fig. 2]와 같고, 이 때 길이는 5가 된다.
 

 

만약 최대 공사 가능 깊이 K = 1로 주어질 경우,

아래 [Fig. 3]과 같이 빨간색 부분의 높이를 9에서 8로 깎으면 길이가 6인 등산로를 만들 수 있다.
 

이 예에서 만들 수 있는 가장 긴 등산로는 위와 같으며, 출력할 정답은 6이 된다.


[제약 사항]

1. 시간 제한 : 최대 50개 테스트 케이스를 모두 통과하는 데 C/C++/Java 모두 3초

2. 지도의 한 변의 길이 N은 3 이상 8 이하의 정수이다. (3 ≤ N ≤ 8)

3. 최대 공사 가능 깊이 K는 1 이상 5 이하의 정수이다. (1 ≤ K ≤ 5)

4. 지도에 나타나는 지형의 높이는 1 이상 20 이하의 정수이다.

5. 지도에서 가장 높은 봉우리는 최대 5개이다.

6. 지형은 정수 단위로만 깎을 수 있다.

7. 필요한 경우 지형을 깎아 높이를 1보다 작게 만드는 것도 가능하다.

[입력]

입력의 맨 첫 줄에는 총 테스트 케이스의 개수 T가 주어지고, 그 다음 줄부터 T개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 지도의 한 변의 길이 N, 최대 공사 가능 깊이 K가 차례로 주어진다.

그 다음 N개의 줄에는 N * N 크기의 지도 정보가 주어진다.

[출력]

테스트 케이스 개수만큼 T개의 줄에 각각의 테스트 케이스에 대한 답을 출력한다.

각 줄은 "#t"로 시작하고 공백을 하나 둔 다음 정답을 출력한다. (t는 1부터 시작하는 테스트 케이스의 번호이다)

출력해야 할 정답은 만들 수 있는 가장 긴 등산로의 길이이다.

입력

10         5 1        9 3 2 3 2  6 3 1 7 5 3 4 8 9 9 2 3 7 7 7 7 6 5 5 8 3 2        1 2 1      2 1 2 1 2 1 …

// 총 테스트 케이스 개수 T = 10 // 첫 번째 테스트 케이스, N = 5, K = 1, 본문 예제 // 지도 정보 // 두 번째 테스트 케이스, N = 3, K = 2 // 지도 정보 // 나머지는 sample_input.txt 참조

sample_input.txt

출력#1 6
#2 3
#3 7
#4 4
#5 2
#6 12
#7 6
#8 7
#9 10
#10 19

sample_output.txt

풀이 해설 : 

1. 맵 입력시 가장 높은 곳 저장

2. DFS 함수 작성 -> 좌표, 높이를 깎는 플래그, 횟수 저장

3. 4방향 검색 

4. 높이 같을때 깍을 수있는 F 플래그 확인

5. 높이차이가 주어진 K 값보다 작으면 현재 값보다 1 만큼 작은 값 설정 [ 최대한 이동해야하기 때문에, 다음 이동 칸이 최대한 높게 깎아야함 ]

6. DFS 함수 진행 시마다 이동값의 최대값 저장

* 처음 실수 : DFS 함수 시작시 시작하는 장소의 방문 배열에 체크를 하지 않음.

 

정답 코드 : DFS 

#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
int mp[9][9];
int visited[9][9];
int k,maxCnt,tc,n,maxVal,ans;
int dy[4]={0,0,1,-1};
int dx[4]={1,-1,0,0};
int checkOver(int y,int x){
    if(y<0 || x<0 || y>=n || x>=n | visited[y][x]==1) return 1;
    else return 0;
}
void dfs(int y,int x,int f,int cnt){
    int curVal = mp[y][x];
    int nY,nX,nVal;
    visited[y][x]=1;
    for(int i=0; i<4; i++){
        nY=y+dy[i];
        nX=x+dx[i];
        if(checkOver(nY,nX)) continue;
        nVal=mp[nY][nX];
        if(curVal>nVal){
            ans=max(ans,cnt+1);
            visited[nY][nX]=1;
            dfs(nY,nX,f,cnt+1);
            visited[nY][nX]=0;
        }else if((nVal-curVal)<k && f==1){
            ans=max(ans,cnt+1);
            mp[nY][nX]=curVal-1;
            visited[nY][nX]=1;
            dfs(nY,nX,0,cnt+1);
            visited[nY][nX]=0;
            mp[nY][nX]=nVal;
        }
    }
    return;
}
void input(){
    maxVal=-1;
    ans=0;
    cin >> n >> k;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            visited[i][j]=0;
            cin >> mp[i][j];
            maxVal=max(maxVal,mp[i][j]);
        }
    }
}
void func(){
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(mp[i][j]==maxVal){
                dfs(i,j,1,1);
                visited[i][j]=0;
            }
        }
    }
}
int main(){
    cin >> tc;
    for(int i=0; i<tc; i++){
        input();
        func();
        cout << "#" << i+1 << " " << ans << endl;
    }
    return 0;
}