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

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.


N*N 크기의 정사각형 모양의 방에 사람들이 앉아 있다.

점심을 먹기 위해 아래 층으로 내려가야 하는데, 밥을 빨리 먹기 위해 최대한 빠른 시간 내에 내려가야 한다.

방 안의 사람들은 P로, 계단 입구를 S라고 했을 때 [Fig. 1]은 사람의 위치와 계단 입구의 위치를 표시한 모습이다.

[Fig. 1]

 

이동 완료 시간은 모든 사람들이 계단을 내려가 아래 층으로 이동을 완료한 시간이다.

사람들이 아래층으로 이동하는 시간은 계단 입구까지 이동 시간과 계단을 내려가는 시간이 포함된다.


    ① 계단 입구까지 이동 시간
        - 사람이 현재 위치에서 계단의 입구까지 이동하는데 걸리는 시간으로 다음과 같이 계산한다.
        - 이동 시간(분) = | PR - SR | + | PC - SC |
          (PR, PC : 사람 P의 세로위치, 가로위치, SR, SC : 계단 입구 S의 세로위치, 가로위치)

    ② 계단을 내려가는 시간
        - 계단을 내려가는 시간은 계단 입구에 도착한 후부터 계단을 완전히 내려갈 때까지의 시간이다.
        - 계단 입구에 도착하면, 1분 후 아래칸으로 내려 갈 수 있다.
        - 계단 위에는 동시에 최대 3명까지만 올라가 있을 수 있다.
        - 이미 계단을 3명이 내려가고 있는 경우, 그 중 한 명이 계단을 완전히 내려갈 때까지 계단 입구에서 대기해야 한다.
        - 계단마다 길이 K가 주어지며, 계단에 올라간 후 완전히 내려가는데 K 분이 걸린다.


사람의 위치와 계단 입구의 위치 및 계단의 길이 정보가 표시된 N*N 크기의 지도가 주어진다.

이때, 모든 사람들이 계단을 내려가 이동이 완료되는 시간이 최소가 되는 경우를 찾고,

그 때의 소요시간을 출력하는 프로그램을 작성하라.


[예시]

방의 한 변의 길이 N 이 5인 지도가 [Fig. 2]와 같이 주어진 경우를 생각해보자.

지도 내에 1 은 사람을 나타내고, 2 이상 10 이하의 숫자는 계단의 입구를 나타내며 해당 숫자는 계단의 길이를 의미한다.

[Fig. 2]에는 사람 6명이 있고, 계단은 2개가 있으며 길이는 각각 3과 5이다.
 

[Fig. 2]

다음은 이동 완료되는 시간이 최소가 되는 경우 중 하나이다.

    - 1번, 2번, 3번 사람은 길이가 3인 1번 계단을 통해 이동

    - 4번, 5번, 6번 사람은 길이가 5인 2번 계단을 통해 이동

이 경우, 모든 사람이 계단을 내려가 이동 완료하는 최소 시간은 9분이다.

다른 예시로, 한 변의 길이가 N인 방에 [Fig. 3]과 같이 배치되어 있는 경우를 생각해보자.

지도 내에 1 은 사람을 나타내고, 2 이상 10 이하의 숫자는 계단의 입구를 나타내며 해당 숫자는 계단의 길이를 의미한다.

 

[Fig. 3]

 

다음은 이동이 완료되는 시간이 최소가 되는 경우 중 하나이다.

    - 1번, 2번, 3번, 4번 사람은 길이가 2인 1번 계단을 통해 이동

    - 5번, 6번 사람은 길이가 5인 2번 계단을 통해 이동

이 경우, 모든 사람이 계단을 내려가 이동 완료하는 최소 시간은 8분이다.


[제약 사항]

1. 시간제한 : 최대 50개 테스트 케이스를 모두 통과하는데, C/C++/Java 모두 3초

2. 방의 한 변의 길이 N은 4 이상 10 이하의 정수이다. (4 ≤ N ≤ 10)

3. 사람의 수는 1 이상 10 이하의 정수이다. (1 ≤ 사람의 수 ≤ 10)

4. 계단의 입구는 반드시 2개이며, 서로 위치가 겹치지 않는다.

5. 계단의 길이는 2 이상 10 이하의 정수이다. (2 ≤ 계단의 길이 ≤ 10)

6. 초기에 입력으로 주어지는 사람의 위치와 계단 입구의 위치는 서로 겹치지 않는다.

 

문제접근법.

1. 예시를 이해하면, 한 사람이 계단을 내려가기 까지 걸리는 시간은,

'이동거리 + 계단거리 + 1(계단 입구에서, 1분후에 아래 칸으로 내려갈 수 있음)' 이다.

2. 계단을 이용하는 사람들의 조합을 구하기 위해서 백트래킹이 필요하다(DFS).

3. 계단에 3명 이상이 있어서, 앞에서 대기하고 있는 사람들이 있다면 들어온 순서대로 들어가야 한다. 자료들을 Sort할 필요가 있다.

 

48번까지만 케이스가 맞는다면, 3번 조건을 이용하지 않아서 그렇다. 문제에서 주어진 조건이 아니어도, 유추해낼 수 있어야 한다. 자신의 생각을 쉽게 풀어낼 수 있다면 코드 작성이 쉬울 것이다. 

 

해설코드(C++).

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
 
int T, N;
int result = -1;
int val;
vector<pair<int, int>> p;
vector<pair<int, int>> s;
vector<int> s_v;
int c0[11] = { 0 };
int c1[11] = { 0 };
 
typedef struct item {
    int idx; 
    int t;
    item(int _i, int _t) : idx(_i), t(_t) {};
}item;
 
struct mf{
    bool operator() (item i1, item i2) { return i1.t < i2.t; }
}myfunc;
 
int func() {
    int p_s[2] = { 0 };
    int ret = 0;
    int finish = 0;
    int check[11] = { 0 };
    memset(check, 0, sizeof(check));
    vector<item> v_i;
 
    for (int i = 0; i < p.size(); i++) {
        int s_idx = -1;
        int s_val = -1;
        int dis = -1;
 
        if (c0[i] == 1) 
            s_idx = 0;
        else
            s_idx = 1;
 
        s_val = s_v.at(s_idx);
        dis = abs(p.at(i).first - s.at(s_idx).first) + abs(p.at(i).second - s.at(s_idx).second) + 1 + s_val;
        v_i.push_back(item(i, dis));
    }
 
    // Simulate
    while (finish < p.size()) {
        sort(v_i.begin(), v_i.end(), myfunc);
        for (int i = 0; i < v_i.size(); i++) {
            if (check[v_i.at(i).idx] == 1)
                continue;
 
            if (c0[v_i.at(i).idx] == 1) {
                if (v_i.at(i).t == s_v.at(0) + 1) {
                    if (p_s[0] < 3)
                        p_s[0]++;
                    else
                        continue;
                }
            }
            else {
                if (v_i.at(i).t == s_v.at(1) + 1) {
                    if (p_s[1] < 3)
                        p_s[1]++;
                    else
                        continue; 
                }
            }
 
            v_i.at(i).t -= 1;
            if (v_i.at(i).t == 0) {
                if (c0[v_i.at(i).idx] == 1)
                    p_s[0]--;
                else 
                    p_s[1]--;
 
                check[v_i.at(i).idx] = 1;
                finish++;
            }
        }
 
        ret++;
        if (ret == result)
            break;
    }
 
    return ret;
}
 
//BACKTRACKING
void comb(int idx) {
    if (idx == N) {
        // Calculate
        if (result == -1)
            result = func();
        else
            result = min(result, func());
 
        return;
    }
 
    c0[idx] = 1;
    comb(idx + 1);
    c0[idx] = 0;
 
    c1[idx] = 1;
    comb(idx + 1);
    c1[idx] = 0;
 
    return;
}
 
 
int main(void) {
    //freopen("input.txt", "r", stdin);
    cin >> T;
    for (int i = 1; i <= T; i++) {
        // Init
        result = -1;
        p.clear();
        s.clear();
        s_v.clear();
 
        cin >> N;
        for (int r = 1; r <= N; r++) {
            for (int c = 1; c <= N; c++) {
                cin >> val;
                // People
                if (val == 1) 
                    p.push_back(make_pair(r, c));
                // Stair
                else if (val > 1) {
                    s.push_back(make_pair(r, c));
                    s_v.push_back(val);
                }
            }
        }
 
        // Comb
        comb(0);
 
        cout << "#" << i << " " << result << endl;
    }
    return 0;
}