SWEA1949.md

등산로 조성

https://swexpertacademy.com/ [1949]

개요

N*N의 map에 숫자들이 주어진다. 가장 높은 숫자부터 출발하여 인접한 4방향(상하좌우)으로 이동하며 수열을 만든다.(중복 비허용) 수열 중 한 개의 숫자에 대해 최대 K만큼 감소시킬 수 있다고 할 때 가장 긴 감소수열을 찾으면 된다.

분석

수열 하나를 생각해보면 조건을 쉽게 생각할 수 있다. 9 7 3 ⑤ 1 이고 K가 3이상이라면 5를 깎아 수열을 성립하게 할 수 있다. 따라서 K가 충분하다고 했을 때 깎는 수의 전의 수와 다음 수의 차이가 2이상이라면 수열이 성립하게 됨을 알 수 있다.

알고리즘

1. 가장 높은 숫자를 찾는다.(1개 이상일 수 있음)

2. 가장 높은 숫자에서 부터 DFS(x, y, sw, l)로 조건에 맞는 부분만 탐색한다.(sw는 숫자하나를 이미 감소시켰다면 해당 숫자의 바로 전의 숫자, 아니라면 0)

3. DFS의 조건은 (방문하지 않았고 (다음 좌표의 숫자<지금 좌표의 숫자) 이고 (안깎았거나 깎았는데 해당 숫자의 바로 전 숫자-1>다음 좌표의 숫자)) 이면 DFS(nx, ny, sw, l+1) 또는 (안깎았고 다음좌표의 숫자-K>지금 좌표의 숫자) 이면 DFS(nx, ny, map(x,y), l+1)이다.

4. 길이가 max 보다 길다면 max갱신

5. 모두 탐색하였다면 종료

소스

#include <stdio.h>
#include <malloc.h>
 
int bang[4][2] = { { -1,0 }, {1,0}, {0,-1}, {0,1} },map[10][10], chk[10][10], N, K, answer;
 
int bc(int r, int c)
{
    if (r >= 0 && r < N && c >= 0 && c < N) return 1;
    return 0;
}
 
void go(int r, int c, int sw, int l)
{
    int i, nr, nc;
    if (l > answer) answer = l;
    chk[r][c] = 1;
    for (i = 0; i <= 3; i++)
    {
        nr = r + bang[i][0];
        nc = c + bang[i][1];
        if (bc(nr, nc) == 1 && chk[nr][nc]==0)
        {
            if (map[r][c] > map[nr][nc] && (sw == 0 || (sw - 1) > map[nr][nc])) go(nr, nc, sw, l + 1);
            else if (sw == 0 && (map[nr][nc]-K)<map[r][c]) go(nr, nc, map[r][c], l + 1);
        }
    }
    chk[r][c] = 0;
}
 
int main()
{
    int T, i, j, k, max;
    scanf("%d", &T);
    for (i = 1; i <= T; i++)
    {
        max = 0;
        answer = 0;
        scanf("%d%d", &N, &K);
        for (j = 0; j < 10; j++)
        {
            for (k = 0; k < 10; k++)
            {
                map[j][k] = 0;
                chk[j][k] = 0;
            }
        }
        for (j = 0; j < N; j++)
        {
            for (k = 0; k < N; k++)
            {
                scanf("%d", &map[j][k]);
                if (max < map[j][k]) max = map[j][k];
            }
        }
        for (j = 0; j < N; j++)
        {
            for (k = 0; k < N; k++)
            {
                if (max == map[j][k]) go(j, k, 0, 1);
 
            }
        }
        printf("#%d %d\n", i, answer);
    }
    return 0;
}