[SWEA] 2383. 점심 식사시간

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5-BEE6AK0DFAVl 

SW Expert Academy

 

문제 이해

사람은 최대 10명이므로, 사람을 기준으로 DFS를 구현해도 충분히 할 수 있다.

문은 2개뿐이므로 사람 별로 문을 선택하면 2^10의 경우가 나온다. 모든 경우를 살펴봐도 시간 limit안에 들어올 수 있다. 그러므로 사람을 기준으로 DFS를 하면 된다.

 

모든 사람이 둘 중 하나의 문을 선택한 후에, 그 정보를 기반으로 시간이 얼마나 걸렸는지를 계산한다. 

그리고 각 시간마다 최대값과 비교해 최대값을 갱신하면 도니다. 

 

사실 아이디어는 금방 내는데, 시간 계산이 좀 어려운 것 같다. 

나는 goDown()이라는 함수를 만들어서 시간을 계산했다. 

int goDown2(void) {

    int t;
    POS ppl_copy[10];
    int st1[100] = { 0, };
    int st2[100] = { 0, };
    int start = 0;

    // ppl의 복사본 생성
    for (int i = 0; i < ppl_cnt; i++) {
        ppl_copy[i] = ppl[i];
    }

    // sort
    qsort(ppl_copy, ppl_cnt, sizeof(ppl[0]), comp);

    for (int i = 0; i < ppl_cnt; i++) {
        if (ppl_copy[i].s == 1) {
            // 1번 계단
            start = ppl_copy[i].d+1;
            while (st1[start] >= 3) {
                start++;
            }
            for (int j = 0; j < st1_len; j++) {
                st1[start + j]++;
            }
        }
        if (ppl_copy[i].s == 2) {
            // 2번 계단
            start = ppl_copy[i].d+1;
            while (st2[start] >= 3) {
                start++;
            }
            for (int j = 0; j < st2_len; j++) {
                st2[start + j]++;
            }
        }
        
        for (t = start; t < 100; t++) {
        if (st1[t] == 0 && st2[t] == 0) break;
        }
        return t;
    }

1. 일단 사람들이 선택한 문에 대한 정보를 갖고 있는 배열 ppl을 복사해서 이를 이용했다 (sort할 거라서)

2. ppl 배열의 요소를 도착한 시간 순서로 정렬한다.

 - 도착한 시간은 선택한 문과 본인의 시작위치를 갖고 계산하면 된다. 이동 시간(분) = | PR - SR | + | PC - SC |

3. 계단 별로 각 시간에 계단에 있는 사람 수를 저장할 수 있는 배열 st1와 st2 를 둔다. 

4. 만약 도착 시간에 st1배열이 3이면, 그 다음부터 3이 아닌 인덱스를 찾는다. 아닌 인덱스를 찾으면 거기부터 계단을 내려가는 시간(st1_len) 만큼 요소 값을 1씩 증가시킨다.

   도착 시간에 st1배열이 0~2이면 거기서 바로 계단 내려가는 표시 (st1_len만큼 1씩 증가시키기) 하면 된다.

5.  st1이나 st2 중에 가장 늦게 1표시가 되어있는 인덱스를 찾는다. 그게 바로 마지막 사람이 계단에서 빠져나간 사람이고, 모든 사람이 계단을 내려간 시간이다. 

 - start에는 마지막 사람이 계단을 내려가기 시작한 시간이 있으므로 거기서부터 하면 뒤에 1이상의 수가 있는데 중간에 0이 끼어들어가서 탐색을 멈추는 경우를 피할 수 있다.  

 

작성 코드(C)

#include <stdio.h>
#include <stdlib.h>

#define ABS(x) (((x)>0) ? (x) : -(x))

 // 입력받을 변수
int N;
int map[12][12];

int min = 0x7fffffff; // 최솟값 저장
typedef struct person {
    int y;
    int x;
    int s; // 선택한 계단
    int d; // 선택한 계단까지의 거리 = 도착 시간
}POS;

POS ppl[10];
int ppl_cnt;

int st1_len, st2_len; // 계단 길이
POS st1_pos, st2_pos; // 계단 위치
int st_cnt;

void initialize(void) {
    min = 0x7fffffff;
    ppl_cnt = 0;
    st1_len = st2_len = st_cnt = 0;
}

void getInput(void) {
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            scanf("%d", &map[i][j]);
            if (map[i][j] == 1) {
                ppl[ppl_cnt].y = i;
                ppl[ppl_cnt].x = j;
                ppl_cnt++;
            }
            if (map[i][j] > 1) {
                if (st_cnt == 0) {
                    st1_pos.y = i;
                    st1_pos.x = j;
                    st1_len = map[i][j];
                }
                else {
                    st2_pos.y = i;
                    st2_pos.x = j;
                    st2_len = map[i][j];
                }
                st_cnt++;
            }
        }
    }
}

int comp(void* a, void* b) {
    POS* p = (POS *)a;
    POS* q = (POS *)b;
    return p->d - q->d;
}

int goDown2(void) {

    int t;
    POS ppl_copy[10];
    int st1[100] = { 0, };
    int st2[100] = { 0, };
    int start = 0;

    // ppl의 복사본 생성
    for (int i = 0; i < ppl_cnt; i++) {
        ppl_copy[i] = ppl[i];
    }

    // sort
    qsort(ppl_copy, ppl_cnt, sizeof(ppl[0]), comp);

    for (int i = 0; i < ppl_cnt; i++) {
        if (ppl_copy[i].s == 1) {
            // 1번 계단
            start = ppl_copy[i].d+1;
            while (st1[start] >= 3) {
                start++;
            }
            for (int j = 0; j < st1_len; j++) {
                st1[start + j]++;
            }
        }
        if (ppl_copy[i].s == 2) {
            // 2번 계단
            start = ppl_copy[i].d+1;
            while (st2[start] >= 3) {
                start++;
            }
            for (int j = 0; j < st2_len; j++) {
                st2[start + j]++;
            }
        }
    }

    for (t = start; t < 100; t++) {
        if (st1[t] == 0 && st2[t] == 0) break;
    }
    return t;
}

void DFS(int idx) {

    // idx >= ppl_cnt
    if (idx >= ppl_cnt) {
        // 맨 끝 사람들까지 정해줌
        int ret = goDown2();
        if (min > ret) min = ret;
        return;
    }

    // 재귀
    ppl[idx].s = 1; // 1번 계단 선택
    ppl[idx].d = ABS(st1_pos.y - ppl[idx].y) + ABS(st1_pos.x - ppl[idx].x); // 거리 계산
    DFS(idx + 1);
    ppl[idx].s = 2; // 2번 계단 선택
    ppl[idx].d = ABS(st2_pos.y - ppl[idx].y) + ABS(st2_pos.x - ppl[idx].x); // 거리 계산
    DFS(idx + 1);
}

int main(void) {

    int T;
    scanf("%d", &T);
    for (int t = 0; t < T; t++) {
        getInput();
        DFS(0);
        printf("#%d %d\n", t + 1, min);
        initialize();
    }
    return 0;
}