2383.점심 식사시간

이번에 풀어볼 문제는 SW Expert의 2383 점심식사시간이다.

SW Expert Academy

어떻게 풀지는 알겠는데 구현과 설계가 생각보다 많이 어려운 문제이다.

이전에 풀어봤던 2477 자동차 정비소와 비슷한 난이도처럼 느껴졌지만 더 어려웠던거 같다.

딱 보면 이렇게 풀면 되는데.. 라는 생각은 드는데 구현이 굉장히 복잡했고 결국 시간안에 풀지 못해서

다른사람의 코드를 공부하는 식으로 진행했다.. 나중에 다시한번 풀어봐야겠다.. ㅠㅠ

참고 블로그 : https://charm-charm.postype.com/post/3602958

 

 

---

 

이 문제의 포인트는 다음과 같다.

1. 사람들이 선택할 수 있는 모든 계단의 경우의 수를 다 진행해야한다

  => 조합 => 재귀함수이용 

 

2. 대기열에 어떤식으로 값을 저장할 것이고 어떤식으로 소요시간의 진행도를 구현할 수 있는지

  => 설계 능력과 개인의 역량이다..

 

 

---

 

< Code 설명 >

#pragma warning(disable:4996)
#include <iostream>
#include <deque>
#include <algorithm>
#include <string.h>
 
#define MAX 11
 
using namespace std;
 
int T, N;
int map[MAX][MAX]; // 맵 저장 변수
int choice[MAX]; // 계단 종류(1번, 2번) 선택
 
deque<pair<int, int>>stair; // 계단 좌표
deque<pair<int, int>>person;// 사람 좌표
 
int person_cnt; // 사람 수
int ans; // 정답 (최단시간)
 
int search(){
    int time[MAX]; // 이동시간 저장 변수 (계단 입구까지 이동에 걸린시간)
    int t = 0;   // 시간의 흐름 변수
    int cnt = 0; // 이동이 완료된 사람 카운트 변수
    deque<int>wait[2]; // 2가지 종류의 계단 입구 대기열
 
    for (int i = 0; i < person_cnt; i++){ // 사람들의 계단까지의 거리 계산
        //계단의 경우 이전 johap 함수에서 선택한 계단과 사람의 거리로 계산함
        time[i] = abs(person[i].first - stair[choice[i]].first) + abs(person[i].second - stair[choice[i]].second);
    }
 
    while (true){
        if (t >= ans) // 흐른 시간이 최소시간보다 크면 굳이 계산할 필요가 없으므로
            return t; // 현재까지의 시간 그냥 리턴
        if (cnt == person_cnt) // 사람 인원수 만큼 전부 이동이 끝났다면 종료
            return t; // 총 걸린 시간 리턴
 
        for (int i = 0; i < 2; i++){ // 계단을 타기 시작하면
            int wait_size = wait[i].size();
            for (int j = 0; j < wait_size; j++){ // 계단 입구에서 기다리는 사람 수 만큼 탐색
                int first = wait[i].front(); // 계단입구에 제일 먼저 서있는 사람의 대기 시간을 저장
                wait[i].pop_front(); // 해당 값을 대기열에서 제거
                first -= 1; // 대기시간 1초 감소
                if (first != 0) // 시간이 지났지만 0초가 아닌경우
                    wait[i].push_back(first); // 해당 값을 다시 대기열에 저장
                else if (first == 0) // 계단을 타는 소요시간 다 끝났다면
                    cnt += 1; // 이동이 완료된 사람 카운트
            }
        }
 
        for (int i = 0; i < person_cnt; i++){ // 계단 입구에 도착하면
// 계단 입구에 오는 사람들은 전부다 push하고 3명보다 작거나 클때로 나눠서 예외처리 하는 것이 point!
            if (t == time[i]){// 이동거리와 걸린시간이 같을 때
                if (wait[choice[i]].size() < 3){ // 해당 사람이 선택한 계단입구의 대기 인원이 3명보다 적다면
                    wait[choice[i]].push_back(map[stair[choice[i]].first][stair[choice[i]].second]); // 대기열에 해당 계단을 탔을 때 걸리는 시간을 저장
                }
                else //대기 인원이 꽉찬 경우
                    // 역시나 대기열에 해당 계단이 걸리는 시간을 넣되, 제일 먼저 계단을 타는 녀석의 계단의 소요시간을 더해줘서 대기시간을 늘려줌// 제일 첫 번째 녀석이 제일 먼저 내려갈 것이고 그 이후에 자리가 빌 것이기 때문이다.
                    wait[choice[i]].push_back(map[stair[choice[i]].first][stair[choice[i]].second] + wait[choice[i]].front()); 
            }
 
        }
        t++; // 시간의 흐름 +1
    }
}
 
void johap(int cnt){
    // 재귀함수 반환 조건 : 사람수 만큼 검색 완료되었다면 최소시간 계산 후 반환
    if (cnt == person_cnt){ // 사람 수 만큼 검색했다면
        int tmp = search(); // 탐색 후 걸린 시간 저장
        ans = min(tmp, ans); // 최소 시간 저장
        return;
    }
    // 실질적인 조합 진행 재귀함수
    choice[cnt] = 0; // 1번 계단을 고른경우
    johap(cnt + 1);  // 다음 계단 선택을 위해 사람수 +1
    choice[cnt] = 1; // 2번 계단을 고른 경우
    johap(cnt + 1); // 다음 계단 선택을 위해 사람수 +1
}
 
void init(){
    memset(map, 0, sizeof(map));
    stair.clear();
    person.clear();
}
 
int main(){
    freopen("2383.txt", "r", stdin);
    cin >> T;
    for (int z = 1; z <= T; z++){
        init();
        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) // 계단 좌표 저장
                    stair.push_back(make_pair(i, j));
                else if (map[i][j] == 1) // 사람 좌표 저장
                    person.push_back(make_pair(i, j));
            }
        }
        person_cnt = person.size(); // 계단을 타는 사람들의 크기 변수
        ans = 987654321; // 정답변수
        johap(0); // 계단입구와 사람들간의 조합 시작 ( 모든 경우의 수 조합으로 체크 )
        cout << "#" << z << " " << ans << "\n";
    }
    return 0;
}