2115. [모의 SW 역량테스트] 벌꿀채취

역테가 얼마 안 남은 이 시점에서!! 적성 공부를 할지 말지 고민하고 있다니...처음에는 알고리즘만 팔거야!!!했었는데. 역시 인간이란ㅜ,ㅠ

1시간 20분 정도 걸렸다. 나는 아직 멀었다. 이정도면 1시간 이하가 나와야 되는데ㅜ,ㅠ

접근법

1. 백트랙킹을 사용하여 A, B 두 사람이 채집할 공간을 찾는다.

A, B 두 사람이 겹침 없이 가로 길이로 M만큼의 공간이 존재할 때의 A, B 두 사람 위치를 구조체에 저장해준다.(아래는 visit배열을 사용해주었으나, 다시 생각하니 필요가 없다.)

2. A, B 위치를 기준으로 길이 M만큼의 조합의 최대 값을 찾는다.

이때는 visit 배열이 필요하다!! 여기서 중요한건 C보다 벌꿀의 합이 작아야 한다. 여기서 C보다 클 때를 딱 찾기 어려워...그냥 C이하에서 모든 값을 구해 최댓값을 비교해주었다.

#include <stdio.h>
#include <string.h>
 
typedef struct {
    int y;
    int x;
}Person;
 
int N, M, C, MA, MAX[2], map[15][15], visit[15][15], visit2[15];
Person P[3] = {0 ,};
 
void Find_MAX(int y, int x, int cur, int n, int per)
{
    if (n > C)
        return;
 
    int num = 0;
    for (int i = x; i < x + M; i++)
    {
        if (visit2[i] == 1)
            num += (map[y][i] * map[y][i]);
    }
 
    if (MAX[per] < num)
    {
        MAX[per] = num;
    }
    for (int i = cur; i < x + M; i++)
    {
        if (visit2[i] == 0)
        {
            visit2[i] = 1;
            Find_MAX(y, x, i, n + map[y][i], per);
            visit2[i] = 0;
        }
    }
    return;
}
 
void DFS(int y, int x, int n)
{
    int Flag = 0;
    if (n == 3)
    {
        memset(visit2, 0, sizeof(visit2)); MAX[1] = -1;
        Find_MAX(P[1].y, P[1].x, P[1].x, 0, 1);
 
        memset(visit2, 0, sizeof(visit2)); MAX[2] = -1;
        Find_MAX(P[2].y, P[2].x, P[2].x, 0, 2);
 
 
        if (MA < MAX[1] + MAX[2])
            MA = MAX[1] + MAX[2];
 
 
        return;
    }
 
    for (int a = y ; a <= N; a++)
    {
        for (int b = x + 1; b <= N; b++)
        {
            //가로 길이가 M 만큼 여유가 있는지.
            if (b + M - 1 > N ||  visit[a][b])
                continue;
 
            //가로 길이가 충분하고, 방문한 곳이 아니면 방문 체크 후 들어간다. 다와서 다시  visit 풀어줌. 길이가 M개니까 M개에 대한 visit체크가 필요함.
 
            for (int i = 0; i < M; i++)
                visit[a][b + i] = n;
 
            P[n].y = a;
            P[n].x = b;
 
            DFS(a, b + M - 1, n + 1);
            
            for (int i = 0; i < M; i++)
                visit[a][b + i] = 0;
 
            P[n].y = 0;
            P[n].x = 0;
        }
        x = 0;
    }
 
    return;
}
 
int main()
{
    int Test_Case;
    scanf("%d", &Test_Case);
 
    for (int T = 1; T <= Test_Case; T++)
    {
        MA = -10;
        memset(P, 0, sizeof(P));
        memset(MAX, -1, sizeof(MAX));
        memset(visit2, 0, sizeof(visit2));
        memset(map, -1, sizeof(map));
        memset(visit, 0, sizeof(visit));
        scanf("%d %d %d", &N, &M, &C);
 
        for (int a = 1; a <= N; a++)
            for (int b = 1; b <= N; b++)
                scanf("%d", &map[a][b]);
 
        DFS(1, 0, 1);
 
        printf("#%d %d\n", T, MA);
    }
 
    return 0;
}