383. [모의 SW 역량테스트] 점심 식사시간

어렵다!!!!!! 약..2시간 20분 컷.

1. 사람의 위치와, 계단의 위치를 저장.

2. 사람이 두 계단으로 가는 모든 경우의 수를 찾아준다.

3. 경우의 수 하나에 대하여, 시간을 구해주면 된다.

시간을 구하는 방법.

1. 경우의 수에 대하여 두 계단에 도착하는 시간을 sort하여 빨리 도착하는 순서대로 나열한다.

2. 반복문을 돌면서 해당 도착 시간이 되면, 계단을 내려가거나 대기하는 변수에 대입해준다.

3. 계단 대기 함수에 앞의 3명은 1식 감소 시키고, 다 내려가면 front변수를 증가시킨다.

#include <stdio.h>
#include <string.h>
 
typedef struct
{
    int y, x;
}point;
 
int map[15][15], visit[11], Stair_num, Perseon_num, N, MIN;
point Stair[3], Person[12];
 
int abs(int a, int b)
{
    return a - b < 0 ? -1 * (a - b) : a - b;
}
 
int len(int y1, int y2, int x1, int x2)
{
    return abs(y1, y2) + abs(x1, x2);
}
 
void Sort(int arr[15], int len)
{
    int MIN = 987654321, Pos = 0, copy[15] = {0,};
 
    for (int i = 0; i < len; i++)
    {
        MIN = 987654321;
        Pos = -1;
        for (int j = 0; j < len; j++)
        {
            if (arr[j] < MIN)
            {
                MIN = arr[j];
                Pos = j;
            }
        }
        if (Pos != -1)
        {
            copy[i] = MIN;
            arr[Pos] = 987654321;
        }
    }
 
    for (int j = 0; j < len; j++)
        arr[j] = copy[j];
}
 
void DFS(int n)
{
    if (n == Perseon_num)
    {
        int Stair_1[2][15] = { 0, }, Stair_2[2][15] = {0, };
        int Stair1_Back = 0, Stair2_Back = 0, t = 0, Stair1_Front = 0, Stair2_Front = 0;
 
        for (int i = 1; i < Perseon_num; i++)
        {
            if (visit[i] == 1)
            {
                Stair_1[0][Stair1_Back++] = len(Stair[1].y, Person[i].y, Stair[1].x, Person[i].x);
            }
            else if(visit[i] == 2)
            {
                Stair_2[0][Stair2_Back++] = len(Stair[2].y, Person[i].y, Stair[2].x, Person[i].x);
            }
        }
 
        Sort(Stair_1[0], Stair1_Back);
        Sort(Stair_2[0], Stair2_Back);
        
        t = 0;
 
        int zero1 = 0, zero2 = 0;
        while (1)
        {
            if (Stair1_Front == Stair1_Back && Stair2_Front == Stair2_Back)
                break;
 
            zero1 = zero2 = 0;
 
            for (int i = 0; i < 3; i++)
            {
                if (Stair1_Front + i < Stair1_Back && Stair_1[1][Stair1_Front + i] > 1)
                {
                    Stair_1[1][Stair1_Front + i]--;
                }
                else if (Stair1_Front + i < Stair1_Back && Stair_1[1][Stair1_Front + i] == 1)
                {
                    Stair_1[1][Stair1_Front + i] = 0;
                    zero1++;
                }
            
                if (Stair2_Front + i < Stair2_Back && Stair_2[1][Stair2_Front + i] > 1)
                {
                    Stair_2[1][Stair2_Front + i]--;
                }
                else if (Stair2_Front + i < Stair2_Back && Stair_2[1][Stair2_Front + i] == 1)
                {
                    Stair_2[1][Stair2_Front + i] = 0;
                    zero2++;
                }
            }
 
            for (int i = 0; i < Stair1_Back; i++)
            {
                if (Stair_1[0][i] == t)
                {
                    Stair_1[1][i] = map[Stair[1].y][Stair[1].x];
                }
 
                if (Stair_1[0][i] > t)
                    break;
            }
 
            for (int i = 0; i < Stair2_Back; i++)
            {
                if (Stair_2[0][i] == t)
                {
                    Stair_2[1][i] = map[Stair[2].y][Stair[2].x];
                }
 
                if (Stair_2[0][i] > t)
                    break;
            }
            Stair1_Front += zero1;
            Stair2_Front += zero2;
        
            t++;
        }
 
        if (t < MIN)
            MIN = t;
 
        return;
    }
 
 
    for (int i = 1; i <= 2; i++)
    {
        visit[n] = i;
        DFS(n + 1);
        visit[n] = 0;
    }
 
    return;
}
 
int main()
{
    int Test_Case;
    scanf("%d", &Test_Case);
 
    for (int T = 1; T <= Test_Case; T++)
    {
        MIN = 987654321;
        Stair_num = Perseon_num = 1;
        memset(map, -1, sizeof(map));
        memset(Stair, 0, sizeof(Stair));
        memset(Person, 0, sizeof(Person));
        memset(visit, 0, sizeof(visit));
 
        scanf("%d", &N);
 
        for (int i = 1; i <= N; i++)
        {
            for (int j = 1; j <= N; j++)
            {
                scanf("%d", &map[i][j]);
                
                if (map[i][j] == 1)
                {
                    Person[Perseon_num].y = i;
                    Person[Perseon_num++].x = j;
                }
                else if (map[i][j] >= 2)
                {
                    Stair[Stair_num].y = i;
                    Stair[Stair_num++].x = j;
                }
            }
        }
 
        DFS(1);
 
        printf("#%d %d\n",T, MIN);
    }
 
    return 0;
}