[SWEA] 2383번 점심 식사시간

2383번 점심 식사시간

문제 링크

 

해결방법

문제를 처음 봤을 때는, BFS 로 계단을 나가야되나??? 라는 생각을 했다

하지만 TC를 보니 거리가 짧은 계단을 이용하는 것이 아니었다

또한 계단의 개수는 2개로 정해져있고, 사람의 수는 10명 이하였다

따라서 예전에 풀었던 스타트와 링크 문제처럼 2개의 그룹으로 나누고 계산을 해야했다

킹치만…!! 계단은 한번에 3명만 내려갈 수 있고, 그 이상의 인원이 도착하면 대기해야 된다는 부분을 솔루션 조차 생각해내지 못했다…. (블로그 참고했음)

꼭 2번 3번 다시 풀어봐야할 문제라고 생각한다 !!!!

 

 

⭐️ 솔루션 ⭐️

• 각각의 사람과 계단1, 계단2의 거리를 구한 뒤, 그 거리를 Person 구조체에 저장한다

  • 원래는 BFS를 통해 거리를 구했지만, 문제에서 맨해튼 거리를 사용하여 거리를 구하라고 제시했으므로 수정함

• DFS 탐색을 통해 최대 10명의 사람들을 두 계단에 배분한다

  • 각 사람들을 벡터로 저장한다
  • 두 그룹이 계단을 내려간 시간 중, 최대값을 구하여 최소시간을 갱신한다

 

문제 조건

• N ≤ 10
• 계단 = 2개 , 사람 수 ≤ 10
• 이동시간 : |x1-x2| + |y1-y2|
• 계단 입구 도착시, 1분 뒤 내려갈 수 있음
• 계단의 길이(K) 만큼 시간이 걸림

 

최대 3명만 계단을 내려갈 수 있는 로직

1. 계단에 먼저 도착하는 순으로 정렬한다

2. 3개의 boolean 배열과 현재 시간(가장 먼저 계단에 도착하는 사람의 거리)을 선언한다

3. 정렬된 인원들을 확인한다

   1. 현재시간 기준으로 계단에 있고 아직 내려가지 않았다면, 빈 used 배열에 계단을 내려가는 시간을 배정하고 내려갔다는 표시를 해준다 (벡터의 거리값을 0으로 바꿔줌)

4. used 배열 모두 -1 을 수행해준다 (계단을 내려감)

5. 시간을 1분 증가시킨다

6. 만약 마지막 인원을 배정해야 한다면?

   1. 그동안 걸린 시간 + 마지막 인원이 계단을 내려가는 시간 + 대기시간 을 반환하고 종료한다

 

 

소스코드

문제 해결 시간 : 2h 30m

메모리 : 12648 KB

시간 : 19 ms

#include <iostream>
#include <math.h>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#define INF 987654321
using namespace std;

// Person 구조체
struct P {
    int x,y;
    int dist1,dist2;
    
    P(){ }
    P(int _x,int _y) : x(_x),y(_y) { }
};

// Stair 구조체
struct S {
    int x,y,time;
    
    S() { }
    S(int _x,int _y,int _time) : x(_x),y(_y),time(_time) { }
};

bool cmp1(P p1, P p2){
    return p1.dist1 < p2.dist1;
}

bool cmp2(P p1, P p2){
    return p1.dist2 < p2.dist2;
}

int testcase;
int n,ans;
int map[11][11];
int kind[11];

int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};

vector<P> person;
vector<S> stair;

int getTime1(vector<P> &v){
    if(v.empty()) return 0;
    
    // 계단에 먼저 도착하는 순서로 정렬
    sort(v.begin(), v.end(), cmp1);
    
    // 계단에는 3명의 사람만 이용 가능
    int used[3] = {0, };
    int time = v[0].dist1;
    
    while(1){
        for(int i=0; i<v.size(); i++){
            if(v[i].dist1 == 0) continue;
            // 도착시간 확인
            if(v[i].dist1 <= time){
                // 빈계단이 있으면 넣음
                for(int j=0; j<3; j++){
                    if(used[j] <= 0){
                        used[j] = stair[0].time;
                        v[i].dist1 = 0;
                        
                        // 마지막 사람이라면?
                        // 그동안 걸린 시간 + 마지막 사람이 계단을 내려가는 시간 + 대기시간
                        if(i == v.size() - 1){
                            return time + stair[0].time + 1;
                        }
                        break;
                    }
                }
                
            }
        }
        // 계단 한 칸씩 내려감
        for(int i=0; i<3; i++){
            used[i]--;
        }
        // 시간 1분 증가
        time++;
    }
}

int getTime2(vector<P> &v){
    if(v.empty()) return 0;
    
    // 계단에 먼저 도착하는 순서로 정렬
    sort(v.begin(), v.end(), cmp2);
    
    // 계단에는 3명의 사람만 이용 가능
    int used[3] = {0, };
    int time = v[0].dist2;
    
    while(1){
        for(int i=0; i<v.size(); i++){
            if(v[i].dist2 == 0) continue;
            // 도착시간 확인
            if(v[i].dist2 <= time){
                // 빈계단이 있으면 넣음
                for(int j=0; j<3; j++){
                    if(used[j] <= 0){
                        used[j] = stair[1].time;
                        v[i].dist2 = 0;
                        
                        // 마지막 사람이라면?
                        // 그동안 걸린 시간 + 마지막 사람이 계단을 내려가는 시간 + 대기시간
                        if(i == v.size() - 1){
                            return time + stair[1].time + 1;
                        }
                        break;
                    }
                }
                
            }
        }
        // 계단 한 칸씩 내려감
        for(int i=0; i<3; i++){
            used[i]--;
        }
        // 시간 1분 증가
        time++;
    }
}

void dfs(int ind,int cnt){
    // 모든 사람의 계단을 정했다면
    if(cnt == person.size()){
        // 계단 나누기
        vector<P> v1,v2;
        for(int i=0; i<person.size(); i++){
            if(kind[i] == 1) v1.push_back(person[i]);
            else v2.push_back(person[i]);
        }
        
        ans = min(ans,max(getTime1(v1),getTime2(v2)));
        return;
    }
    
    // 1번 계단으로 내려가는 경우
    kind[ind] = 1;
    dfs(ind+1,cnt+1);
    
    // 2번 계단으로 내려가는 경우
    kind[ind] = 2;
    dfs(ind+1,cnt+1);
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> testcase;
    for(int t=1; t<=testcase; t++){
        // 초기화
        person.clear();
        stair.clear();
        
        cin >> n;
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                cin >> map[i][j];
                
                if(map[i][j] == 1)
                    person.push_back(P(i,j));
                else if(map[i][j] != 0)
                    stair.push_back(S(i,j,map[i][j]));
            }
        }
        
        // 사람 → 계단 거리 구하기 (맨하튼 거리)
        for(int i=0; i<person.size(); i++){
            person[i].dist1 = abs(person[i].x - stair[0].x) + abs(person[i].y - stair[0].y);
            person[i].dist2 = abs(person[i].x - stair[1].x) + abs(person[i].y - stair[1].y);
        }
        
        // 사람들이 어떤 계단을 사용할지
        ans = INF;
        dfs(0,0);
        
        cout << "#" << t << " " << ans << "\n";
    }
    
    return 0;
}