[C++] SWEA 2383 - 점심 식사시간

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

SW Expert Academy

<풀이>

1. 주어지는 사람들 각각 계단을 선택한다.

2. 선택된 계단들로 나오는데 걸리는 시간을 계산하고, 그 중 가장 최소값을 출력한다.

​

<해법>

1. 주어지는 사람들 각각 계단 선택 방법.

=> 계단 선택은 재귀 함수를 이용하여, 모든 경우를 계산하고 선택된 계단 정보들을 저장합니다.

 

2. 선택된 계단들로 나오는 시간 계산하는 방법.

=> 저는 deque를 이용하였습니다. 계단은 2개이므로 배열로 선언해주었고, deque에 담기는 내용은 계단의 길이입니다.

시간이 증가할 때마다 deque에 담긴 내용을 1씩 감소시켜주고, 0이 될 경우 pop_front를 해주었습니다.

만약 deque의 크기가 4이상일 경우, 앞의 3개의 index의 내용만 1씩 감소시켜주었습니다.

 

3. res + 1

=> 제 코드는 문제에서 주어진 대로 구현하지 않은 단점이 있습니다. 계단에 도착한 즉시 계단 deque안으로 들어가고 값이 1감소합니다.

예를 들면, time=2 일때 계단에 도착하고 time=3일 때부터 계단을 내려가야 하는데, 제 코드는 time=2일 때부터 계단을 내려갑니다.

따라서, 마지막 결과값에 1증가시켜서 출력합니다.

 

#include <iostream>
#include <vector>
#include <deque>
#include <cstring>
using namespace std;
 
//구조체 : 사람
struct people {
    //위치
    int x, y;
    //선택된 계단(0 or 1) 
    int stairNum;
    //선택된 계단 과의 거리
    int distance;
};
 
//구조체 : 계단
struct stair {
    //위치
    int x, y;
    //계단 길이
    int stairLength;
};
 
int N;
int map[10][10];
bool visited[10];
vector<people> p;
vector<stair> s;
int res;
 
void go(int index) {
 
    //모든 사람의 계단 선택이 완료되었을 경우 -> 종료조건
    if (index == p.size()) {
        
        //초기화
        int time = 0;
        memset(visited, false, sizeof(visited));
        deque<int> dq[2];
 
        //시간 계산
        while (true) {
            
            bool all_People_In_Stair = true;
            for (int i = 0; i < p.size(); i++) {
                if (!visited[i]) {
                    all_People_In_Stair = false;
                }
            }
 
            //모든 사람이 계단 안에 들어갔고 && 0번 계단에 사람이 없고 && 1번 계단에 사람이 없을 경우 -> 종료
            if (all_People_In_Stair && dq[0].empty() && dq[1].empty()) {
                break;
            }
 
            //각각 사람 탐색
            for (int i = 0; i < p.size(); i++) {
                //계단에 이미 들어간 사람일 경우, continue
                if (visited[i]) {
                    continue;
                }
 
                //계단에 도착하였을 시, 계단 deque에 "계단 길이" 넣어주기
                if (p[i].distance == time) {
                    if (p[i].stairNum == 0) {
                        dq[0].push_back(s[0].stairLength);
                        visited[i] = true;
                    }
                    else {
                        dq[1].push_back(s[1].stairLength);
                        visited[i] = true;
                    }
                }
            }
 
            //2개 계단 모두 탐색
            for (int i = 0; i < 2; i++) {
 
                //계단에 사람이 있다면
                if (!dq[i].empty()) {
 
                    //계단 deque에 사람이 4명 이상일 경우
                    if (dq[i].size() >= 4) {
 
                        //앞의 3명만 움직이기
                        for (int j = 0; j < 3; j++) {
                            dq[i][j]--;
                        }
                    }
                    //계단 deque에 사람이 3명 이하일 경우
                    else {
 
                        //계단에 있는 사람 전부 움직이기
                        for (int j = 0; j < dq[i].size(); j++) {
                            dq[i][j]--;
                        }
                    }
 
                    for (int j = 0; j < dq[i].size(); j++) {
 
                        //계단을 다 내려간 사람이 있을 경우
                        if (dq[i][j] == 0) {
 
                            //계단 deque에서 제거
                            dq[i].pop_front();
 
                            //index 맞춰주기
                            j--;
                        }
                    }
                }
            }
 
            //시간 증가
            time++;
        }
 
        //결과 저장
        if (res == -1 || time < res) {
            res = time;
        }
 
        //종료
        return;
    }
 
    //각 사람마다 0번 계단 또는 1번 계단 선택
    for (int i = 0; i <= 1; i++) {
        //계단 번호 저장
        p[index].stairNum = i;
        //계단 과의 거리 저장
        p[index].distance = abs(p[index].x - s[i].x) + abs(p[index].y - s[i].y);
 
        go(index + 1);
    }
    return;
}
 
int main() {
    int test_case;
    int T;
 
    cin >> T;
 
    for (test_case = 1; test_case <= T; test_case++) {
 
        //초기화
        memset(map, 0, sizeof(map));
        res = -1;
        p.clear();
        s.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) {
                    p.push_back({ i,j,0,0 });
                }
                //계단일 경우, 계단 벡터에 저장
                else if (map[i][j] > 1) {
                    s.push_back({ i,j,map[i][j] });
                }
            }
        }
 
        //각 사람마다 0번 계단 또는 1번 계단 선택(재귀함수 이용) 후 시간 계산
        go(0);
 
        //출력
        cout << "#" << test_case << " " << res + 1 <<"\n";
 
        
        /*결과에 '+1'을 해준 이유는 계단에 도착한 사람이 바로 계단에 들어가서 그렇습니다*/
        /*문제에서 주어진 대로 정확히 구현하지 못한 코드입니다. 참고로만 봐주시면 감사하겠습니다 :)*/
    }
 
    return 0;
}
 

 

재귀함수와 구현에 대해 알아볼 수 있는 문제였습니다.