모의 SW 등산로 조성 소스

/*

제약사항

50개 테스트 3초

3<=N<=8

1<=K<=5

지형의 높이는 1 이상 20 이하의 정수

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

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

등산로 만드는 규칙

조건 1. 최대한 긴 등산로 건설

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

조건 3. 등산로는 낮은 지형에서 높은 지형으로 가로 또는 세로로 연결이 되어야 한다. 즉, 높이가 같은 곳, 낮은 곳, 대각선 방향의 연결은 불가

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

*/

#include <stdio.h>

#define Size 10

int N, K;

int map[Size][Size];

int visit[Size][Size];

//맵에서 가장 높은 봉우리의 높이

int heightest; 

//정답을 저장하는 변수

int ans;

//상, 하, 좌, 우 이동을 위한 배열

int dir[4][2] = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

typedef struct info{

int h, w; //맵상의 위치

int height; //(h,w) 지점의 높이

int usedK; //공사를 진행한 적이 있다면(1) 아니면(0)

int len; //현재까지의 등산로 길이

};

void sol(info cur)

{

//현재 등산로 길이가 정답이 저장된 값보다 길다면 ans에 가장 긴 값을 저장

ans = ans > cur.len ? ans : cur.len;

//상 하 좌 우 탐색

for (int d = 0; d < 4; d++)

{

//현재 위치 (curH, curW)에 이동 방향을 더해 다음 방문할 위치와 높이 구하기

info nxt = cur;

nxt.h += dir[d][0];

nxt.w += dir[d][1];

nxt.height = map[nxt.h][nxt.w];

//주어진 맵의 사이즈의 범위를 벗어날 경우 탐색을 이어갈 수 없음

if (nxt.h < 0 || nxt.h >= N || nxt.w < 0 || nxt.w >= N) continue;

//이미 방문을 한 경우 탐색을 이어갈 수 없음

if (visit[nxt.h][nxt.w]) continue;

//방문 예정인 위치의 높이가 현재의 높이보다 작은 경우

if (nxt.height < cur.height)

{

//방문 표시

visit[nxt.h][nxt.w] = 1;

//등산로 길이를 1증가

nxt.len++;

//nxt를 기점으로 다음 탐색을 위해 함수 호출

sol(nxt);

//다시 방문 표시를 해제

visit[nxt.h][nxt.w] = 0;

}

// 다음에 갈 곳의 높이가 현재의 높이보다 크거나 같은 경우

else

{

//현재까지 공사가 이루어지지 않았고

//다음 높이에 대해 K 만큼 공사를 했을 때 현재보다 작을 경우에만 가능

if (!cur.usedK && nxt.height - K < cur.height)

{

visit[nxt.h][nxt.w] = 1;

nxt.len++;

//공사했음을 표시

nxt.usedK = 1;

//현재 높이보다 1만 작게 깎아야 가장 긴 등산로를 만들 수 있다.

nxt.height = cur.height - 1;

sol(nxt);

visit[nxt.h][nxt.w] = 0;

}

}

}

return;

}

int main()

{

int T;

scanf(" %d", &T);

for (int t = 1; t <= T; t++)

{

scanf(" %d %d", &N, &K);

//초기화 

heightest = ans = 0;

for (int i = 0; i < N; i++)

{

for (int j = 0; j < N; j++)

{

scanf(" %d", &map[i][j]);

//맵에서 가장 높은 봉우리 찾기

heightest = heightest > map[i][j] ? heightest : map[i][j];

}

}

for (int i = 0; i < N; i++)

{

for (int j = 0; j < N; j++)

{

//가장 높은 봉우리일 경우에만 탐색을 시작

if (heightest == map[i][j])

{

//방문을 표시하고

visit[i][j] = 1;

//위치(i, j), 높이, 공사 진행하지 않음(0), 현재 등산로 길이(1)

info cur = { i, j, map[i][j], 0, 1 };

//cur를 기점으로 탐색하기 위해 함수 호출

sol(cur);

//다시 방문 표시 해제

visit[i][j] = 0;

}

}

}

printf("#%d %d\n", t, ans);

}

return 0;

}