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

SWExpertAcademy의 점심 식사시간(2383) 문제이다.

[ 문제풀이 ]

1) 문제를 정리해보면, 주어진 사람들이 2개의 계단 중 하나의 계단을 선택해서 계단을 내려갈 때, 계단을 가장 빨리 내려갈

   수 있는 시간을 구하는 것이 문제이다.

   본인은 이 문제를 보고 가장 먼저 구현한 것인 '중복순열' 이었다. 중복순열이 갑자기 왜 나왔는지 왜 조합이 아닌

   순열이여야 하는지부터 알아보자.

   사람들이 2개의 계단 중에서 한 개의 계단을 선택해야 한다. 즉, 사람이 N명이라고 가정했을 경우, N명이 모두 1번계단

   으로만 갈 수도 있고, 2번 계단으로만 갈 수도 있고 적절히 분배해서 갈 수도 있다.

   이 과정을 위해서 순열을 구현해주었다.

   순열인 이유는, 순서에 영향을 미치기 때문이다.

   예를 들어서, 사람이 5명이고, 계단을 '1', '2'로 표시했을 때 5명의 사람이 계단을 선택하는 경우는 굉장히 많겠지만

   그 중 몇개만 뽑아보자면 이런 경우들이 존재할 것이다.

   { 1, 1, 1, 1, 1 } → 5명이 모두 '1'번 계단을 이용

   { 1, 1, 1, 1, 2 } → 1 ~ 4번 사람은 '1'번계단을, 5번 사람은 '2'번 계단을 이용

   { 1, 1, 1, 2, 1 } → 1 ~ 3, 5번 사람은 '1'번 계단을, 4번 사람은 '2'번 계단을 이용.

   이 때, 위에서 2번 Case와 3번 Case를 보자. 2번과 3번 Case의 답은 서로 다를까? 다를 것이다. 왜냐하면

   사람마다 계단까지 가는데 걸리는 거리가 존재하고, 계단을 내려가는데 걸리는 시간 또한 동일하지 않기 때문에

   당연하게도 다른 결과가 나올 것이다. 이 부분 때문에 조합이 아닌 순열을 구현해 주었다.

   조합이었다면, { 1, 1, 1, 1, 2 } 를 뽑는 순간, { 1, 1, 1, 2, 1 } 은 절대 뽑지 않게 될 것이다. 이렇게 되면 원하는 정답을

   도출해 낼 수 없기 때문이다.

   자연스럽게 중복순열인 이유는 알게 됬을 것이다. '1'번계단 누군가 한 명이 이용한다고 해서, 더 이상 이용을 못하게

   하는 말도 안 되는 상황을 만들어서는 안되기 때문이다.

   아직 중복순열을 잘 모른다면 아래의 글을 읽고 오도록 하자.

   [ 중복순열 구현하기(Click) ]

2) 1)번 과정을 완성했다면 아마 우리는 문제에서 사람들이 계단을 선택하는 부분을 구현한 것이 될 것이다.

   그렇다면 이제 본격적으로 사람을 움직이고 계단을 내려가는 부분을 알아보자.

   먼저 본인은 이 문제를 해결하기 위해서 2개의 구조체를 만들어 주었다.

   바로 사람의 정보를 저장하는 구조체와, 계단의 정보를 저장하는 구조체이다.

  

   먼저 '계단' 구조체에 대해서 알아보자.

   계단 구조체는 4개의 변수를 갖는다. 계단의 좌표를 나타내는(x, y)값, 계단의 길이를 나타내는 'Len',

   현재 계단을 내려가고 있는 사람의 수를 Count해주는 'Num' 변수이다.

   다음은 '사람' 구조체이다.

   사람 구조체는 사람의 좌표를 나타내는(x, y)값, 계단 까지 가는데 걸리는 시간을 저장하는 'MoveTime',

   계단을 내려가기 시작하는 시간인 'StartTime', 계단을 모두 내려가는 시간을 저장하는 'EndTime',

   계단을 모두 내려갔는지 아닌지를 Check해주는 'Finish'변수이다.

   이 2개의 구조체를 이용해서 지금부터 계산을 해 볼 것이다.

   현재까지 우리가 해놓은 일은, 사람이 계단을 선택하는 과정까지만 구현을 해 놓았다.

   지금부터 계산할 내용들을 정리해보면 다음과 같다.

   1. 사람과 그 사람이 선택한 계단 사이의 거리를 구해준다.

   - 지금부터는 반복문이 한 번 돌때마다 시간이 +1 이 되는 무한루프 안에서 특정 종료조건을 만족할 때 까지 반복.

   2. 현재 시간이 계단에 도착하는 사람이 있으면 계단 대기 열에 넣어준다.

   3. 계단을 이용할 수 있다면 계단을 이용하게 만들어준다.

   이 과정을 이제부터 구체적으로 알아보자.

   1. 사람과 그 사람이 선택한 계단 사이의 거리를 구해준다.

    - 이 부분은 문제에서 제시한 방법으로 거리를 구해주기만 하면 된다. 하지만 ! 본인은 이 거리에 + 1을 해서 저장해주었다.

      왜냐하면 어차피 계단에 도착한다고 한들, 1분이라는 대기시간이 필요하게 된다. 즉, 이 시간을 없애버리기 위해서

      애초에 거리를 구할 때 + 1을 해서 저장해 주었다.

      어디에 저장을 할까? 바로 사람 구조체에 있는 'MoveTime' 변수에 저장해 주었다.

   2 & 3. 현재 시간에 계단에 도착하는 사람이 있으면 계단 대기열에 넣어준다.

    - 본인은 각 계단마다 대기열 역할을 해줄 Queue를 만들어 주었다. 그리고, 계단에 도착하는 사람이 있으면

      현재 대기열이 있든 없든 무조건 대기열 Queue에 넣어주었다. 일단 넣어준 후에, 만약 계단이 최대인원을 초과하지

      않았다면 큐에서 앞에서 하나씩 빼주면서 계단에 사람을 올려주었다.

     

   그리고 마지막은 종료조건이다. 언제 종료하면 될까? 바로 모든 사람이 계단을 다 내려가면 종료시키면 된다.

   그리고 걸린 시간을 기존의 시간과 비교해서 갱신시켜 주면 된다.

 

   이번 글에서는 정말로 문제에 맞게, 1초마다 계단으로 사람을 옮겨주고, 계단을 이용하지 못할 상황이라면 대기열에서

   기다리고, 계단의 길이만큼 계단을 내려가는 것을 모든 1초마다 하나하나 구현해 보았다.

   이렇게 구현해도 pass를 받을 수 있다. 다음 글에서는 보다 간편한 방법으로 푸는 것을 알아보도록 하자.

[ 소스코드 ]

#include<iostream>
#include<cmath>
#include<queue>
 
#define endl "\n"
#define MAX 10
using namespace std;
 
struct STAIR        // 계단 구조체
{
    int x;            // x좌표
    int y;            // y좌표
    int Len;        // 계단의 길이
    int Num;        // 현재 이용자 수
};
 
struct PERSON        // 사람 구조체
{
    int x;            // x좌표
    int y;            // y좌표
    int MoveTime;    // 계단까지 가는데 걸리는 시간
    int StartTime;    // 계단을 이용하기 시작하는 시간
    int EndTime;    // 계단 이용을 끝내는 시간
    bool Finish;    // 계단을 모두 내려갔는지 Check.
};
 
int N, P_Num, Answer;
int MAP[MAX][MAX], Select[MAX];
PERSON Person[MAX];            // '사람' 구조체 배열
STAIR Stair[2];                // '계단' 구조체 배열
queue<int> Waiting[2];        // 2개의 계단에서 대기열 역할을 해주는 Queue.
 
int Min(int A, int B) { if (A < B) return A; return B; }
 
void Initialize()
{
    Answer = 987654321;
}
 
void Init()
{
    for (int i = 0; i < P_Num; i++)
    {
        Person[i].MoveTime = Person[i].StartTime = Person[i].EndTime = -1;
        Person[i].Finish = false;
    }
    for (int i = 0; i < 2; i++)
    {
        while (Waiting[i].empty() == 0) Waiting[i].pop();
        Stair[i].Num = 0;
    }
}
 
void Input()
{
    int P_Idx, Idx;
    P_Idx = Idx = 0;
 
    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[P_Idx].x = i;
                Person[P_Idx].y = j;
                Person[P_Idx].MoveTime = Person[P_Idx].StartTime = Person[P_Idx].EndTime = -1;
                Person[P_Idx].Finish = false;
                P_Idx++;
            }
            else if (MAP[i][j] >= 2)
            {
                Stair[Idx].x = i;
                Stair[Idx].y = j;
                Stair[Idx].Len = MAP[i][j];
                Stair[Idx].Num = 0;
                Idx++;
            }
        }
    }
    P_Num = P_Idx;
}
 
int Dist(int P_Idx, int S_Idx)
{
    int dx = abs(Person[P_Idx].x - Stair[S_Idx].x);
    int dy = abs(Person[P_Idx].y - Stair[S_Idx].y);
 
    return (dx + dy) + 1;
}
 
void CompleteMoving(int Time)
{
    /* 
    계단을 모두 내려간 사람들을 체크해주는 함수. 
    * 내려간 사람의 Finish를 'true'로 설정.
    * 계단의 이용자수를 -1.
    */
    for (int i = 0; i < P_Num; i++)
    {
        if (Person[i].EndTime == Time)
        {
            Person[i].Finish = true;
            Stair[Select[i]].Num--;
        }
    }
}
 
bool Check()
{
    /* 무한루프의 종료조건을 위한 Check 함수. */
    for (int i = 0; i < P_Num; i++)
    {
        if (Person[i].Finish == false) return false;
    }
    return true;
}
 
void GoToStairs(int Time)
{
    /* 현재 'Time'초에 계단에 도착하는 사람을 계단의 대기열에 넣어주는 함수. */
    for (int i = 0; i < P_Num; i++)
    {
        if (Person[i].MoveTime == Time)
        {
            int Idx = Select[i];
            Waiting[Idx].push(i);
        }
    }
}
 
void Func()
{
    /* Simulation 하는 함수. */
    /* 가장 먼저, 사람과 그 사람이 선택한 계단과의 거리를 구해준다. */
    for (int i = 0; i < P_Num; i++)
    {
        Person[i].MoveTime = Dist(i, Select[i]);
    }
    
    int Time = 0;
    while (1)
    {
        CompleteMoving(Time);
        if (Check() == true) break;
        
        GoToStairs(Time);
 
        for (int i = 0; i < 2; i++)
        {
            int Stair_Len = Stair[i].Num;
            int Wait_Len = Waiting[i].size();
            if (Stair_Len < 3 && Wait_Len > 0)
            {
                while (Waiting[i].empty() == 0)
                {
                    if (Stair[i].Num == 3) break;
                    Person[Waiting[i].front()].StartTime = Time;
                    Person[Waiting[i].front()].EndTime = Time + Stair[i].Len;
                    Stair[i].Num++;
                    Waiting[i].pop();
                }
            }
        }
        Time++;
    }
 
    Answer = Min(Answer, Time);
}
 
void DFS(int Cnt)
{
    if (Cnt == P_Num)
    {
        /* 모든 사람이 계단 선택을 완료했을 경우 Simulation 시작. */
        Init();
        Func();
        return;
    }
 
    /* 중복 순열을 구하는 과정 */
    for (int i = 0; i < 2; i++)
    {
        Select[Cnt] = i;
        DFS(Cnt + 1);
    }
}
 
void Solution()
{
    /* 중복 순열을 구하는 것으로 문제 풀이를 시작. */
    DFS(0);
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << "#" << T << " " << Answer << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}