SWEA [모의 SW 역량테스트] 점심 식사시간 C++

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5-BEE6AK0DFAVl&categoryId=AV5-BEE6AK0DFAVl&categoryType=CODE&problemTitle=모의&orderBy=PASS_RATE&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=2&&&&&&&&& 

 

최종 코드

• GitHub -> https://github.com/hwayeon351/SWEA-Algorithms/blob/main/SWEA2383.cpp

GitHub - hwayeon351/SWEA-Algorithms: SWEA 알고리즘 소스 코드 모음

//
//  main.cpp
//  SWEA2383
//
//  Created by Hwayeon on 2021/10/20.
//

#include <iostream>
#include <math.h>
#include <vector>
#include <queue>
#include <deque>
using namespace std;

int N;
int room[10][10] = {0, };

struct Person{
    int x;
    int y;
    int stair;
    int dis;
    int move;
};
struct Stairs{
    int x;
    int y;
    int K = 0;
    deque<Person> users;
    queue<Person> waitings;
};
Person person;
Stairs stair;
vector<Stairs> stairs;
vector<Stairs> copy_stairs;
vector<Person> people;
vector<Person> copy_people;

int min_time = -1;

void move_people(){
    copy_people = people;
    copy_stairs = stairs;
    int sec = 0;
    int cnt = 0;
    bool check = false;
    while(true){
        sec++;
        //1. 사람들 계단으로 이동
        for(int p=0; p<copy_people.size(); p++){
            if(copy_people[p].move > copy_people[p].dis) continue;
            copy_people[p].move ++;
            //계단 도착 -> 해당 계단 웨이팅에 들어갔다가 1초 후 계단을 내려가기 시작한다
            if(copy_people[p].move == copy_people[p].dis+1){
                person = copy_people[p];
                person.move = 0;
                copy_stairs[copy_people[p].stair].waitings.push(person);
            }
        }

        //2. 계단 이동 완료된 사람 체크
        while((!copy_stairs[0].users.empty() && copy_stairs[0].users.front().move == copy_stairs[0].K) || (!copy_stairs[1].users.empty() && copy_stairs[1].users.front().move == copy_stairs[1].K)){
            if(!copy_stairs[0].users.empty() && copy_stairs[0].users.front().move == copy_stairs[0].K){
                copy_stairs[0].users.pop_front();
                cnt++;
            }
            if(!copy_stairs[1].users.empty() && copy_stairs[1].users.front().move == copy_stairs[1].K){
                copy_stairs[1].users.pop_front();
                cnt++;
            }
            if(cnt == people.size()){
                check = true;
                break;
            }
        }
        //모든 사람이 이동 완료한 경우, while문 종료
        if(check) break;
        
        //3. 계단에 도착한 사람 추가
        while(copy_stairs[0].users.size() < 3 && copy_stairs[0].waitings.size() > 0){
            person = copy_stairs[0].waitings.front();
            copy_stairs[0].users.push_back(person);
            copy_stairs[0].waitings.pop();
        }
        while(copy_stairs[1].users.size() < 3 && copy_stairs[1].waitings.size() > 0){
            person = copy_stairs[1].waitings.front();
            copy_stairs[1].users.push_back(person);
            copy_stairs[1].waitings.pop();
        }
        
        //4. 계단에 있는 사람들 한 칸씩 내려가기
        for(int s=0; s<2; s++){
            for(int p=0; p<copy_stairs[s].users.size(); p++){
                copy_stairs[s].users[p].move++;
            }
        }
    }
    if(min_time == -1) min_time = sec;
    else if(min_time > sec) min_time = sec;
}

void decide_stairs(int p){
    if(p == people.size()){
        move_people();
        return;
    }
    for(int s=0; s<2; s++){
        people[p].stair = s;
        people[p].dis = abs(people[p].x - stairs[s].x) + abs(people[p].y - stairs[s].y);
        decide_stairs(p+1);
    }
}

int main(int argc, const char * argv[]) {
    int test_case;
    int T;
    cin >> T;
    
    for(test_case=1; test_case<=T; ++test_case){
        stairs.clear();
        people.clear();
        min_time = -1;
        
        cin >> N;
        for(int y=0; y<N; y++){
            for(int x=0; x<N; x++){
                cin >> room[y][x];
                if(room[y][x] == 1){
                    person.stair = 0;
                    person.x = x;
                    person.y = y;
                    person.dis = 0;
                    person.move = 0;
                    people.push_back(person);
                }
                else if(room[y][x] > 1){
                    stair.x = x;
                    stair.y = y;
                    stair.K = room[y][x];
                    stair.users.clear();
                    stairs.push_back(stair);
                }
            }
        }
        decide_stairs(0);
        cout << "#" << test_case << " " << min_time << endl;
    }
    return 0;
}

---

풀이 과정

풀이 시간 2시간 7분

사람들이 계단이 있는 곳까지 이동하고 계단에 도착해서 계단을 내려가는 과정을 구현하는데 각각의 과정이 처리되는 시간에 유의해야 한다.

예를 들어 계단이 있는 곳까지 도착하면, 1분 후 계단을 내려가기 시작하는 것과 같은 경우이다.

문제에 주어진 예시에서 시간에 따라 발생하는 로직을 그대로 잘 구현해야 정답을 받을 수 있다.

#include <iostream>
#include <math.h>
#include <vector>
#include <queue>
#include <deque>
using namespace std;

int N;
int room[10][10] = {0, };

struct Person{
	//현재 위치
    int x;
    int y;
    
    //이용할 계단
    int stair;
    
    //처음 위치에서 이용할 계단까지의 거리
    int dis;
    
    //현재 이동한 거리
    //계단에 도착하지 않은 경우, move는 계단에 도달하기까지 간 거리를 의미
    //계단에 도착한 경우, move는 내려간 계단 수를 의미
    int move;
};
struct Stairs{
	//계단 위치
    int x;
    int y;
    //계단 수
    int K = 0;
    //계단에 있는 사람들을 담는 덱
    deque<Person> users;
    //계단을 이용하기 위해 기다리는 사람들을 담는 큐
    queue<Person> waitings;
};
Person person;
Stairs stair;

//입력으로 주어진 계단의 상태를 담는 벡터
vector<Stairs> stairs;
//시뮬레이션에서 사용할 계단의 상태를 담는 벡터
vector<Stairs> copy_stairs;
//입력으로 주어진 사람들의 상태를 담는 벡터
vector<Person> people;
//시뮬레이션에서 사용할 사람들의 상태를 담는 벡터
vector<Person> copy_people;

int min_time = -1;

void move_people(){
	//시뮬레이션을 위해 people과 stairs를 복사한다
    copy_people = people;
    copy_stairs = stairs;
    
    //현재 시간
    int sec = 0;
    //이동 완료한 사람 수
    int cnt = 0;
    //check = true -> 모든 사람들이 이동을 완료한 경우, check = false -> 아직 이동을 완료하지 못한 사람이 있는 경우
    bool check = false;
    
    while(true){
        sec++;
        //1. 계단에 도착하지 않은 사람들을 계단이 있는 위치로 1칸씩 이동한다
        for(int p=0; p<copy_people.size(); p++){
        	//이미 계단에 도착한 사람인 경우, 무시한다
            if(copy_people[p].move > copy_people[p].dis) continue;
            
            //1칸 이동
            copy_people[p].move ++;
            //계단에 도착하고 1초가 지난 경우 -> 계단에 내려가기 위해 대기줄에 세운다
            if(copy_people[p].move == copy_people[p].dis+1){
                person = copy_people[p];
                //move를 0으로 바꾸고 대기줄에 세운다
                person.move = 0;
                copy_stairs[copy_people[p].stair].waitings.push(person);
            }
        }

        //2. 계단 이동 완료된 사람 체크
        while((!copy_stairs[0].users.empty() && copy_stairs[0].users.front().move == copy_stairs[0].K) || (!copy_stairs[1].users.empty() && copy_stairs[1].users.front().move == copy_stairs[1].K)){
            //첫번째 계단을 이용하는 사람이 있고 계단을 계단을 모두 내려온 사람이 있다면, 해당 사람은 이동 완료
            if(!copy_stairs[0].users.empty() && copy_stairs[0].users.front().move == copy_stairs[0].K){
                copy_stairs[0].users.pop_front();
                cnt++;
            }
            //두번째 계단을 이용하는 사람이 있고 계단을 계단을 모두 내려온 사람이 있다면, 해당 사람은 이동 완료
            if(!copy_stairs[1].users.empty() && copy_stairs[1].users.front().move == copy_stairs[1].K){
                copy_stairs[1].users.pop_front();
                cnt++;
            }
            //모든 사람이 이동 완료한 경우, check를 true로 바꾸고 while문을 빠져나간다
            if(cnt == people.size()){
                check = true;
                break;
            }
        }
        //모든 사람이 이동 완료한 경우, while문 종료
        if(check) break;
        
        //3. 계단 이용 대기자 계단에 추가
        //현재 0번째 계단에 올라와있는 사람이 3명 미만이고 0번째 계단을 이용하고자 하는 대기자가 있는 경우,
        while(copy_stairs[0].users.size() < 3 && copy_stairs[0].waitings.size() > 0){
            person = copy_stairs[0].waitings.front();
            copy_stairs[0].users.push_back(person);
            copy_stairs[0].waitings.pop();
        }
        //현재 1번째 계단에 올라와있는 사람이 3명 미만이고 1번째 계단을 이용하고자 하는 대기자가 있는 경우,
        while(copy_stairs[1].users.size() < 3 && copy_stairs[1].waitings.size() > 0){
            person = copy_stairs[1].waitings.front();
            copy_stairs[1].users.push_back(person);
            copy_stairs[1].waitings.pop();
        }
        
        //4. 계단에 있는 사람들 한 칸씩 내려가기
        for(int s=0; s<2; s++){
            for(int p=0; p<copy_stairs[s].users.size(); p++){
                copy_stairs[s].users[p].move++;
            }
        }
    }
    //최소 시간 갱신
    if(min_time == -1) min_time = sec;
    else if(min_time > sec) min_time = sec;
}

void decide_stairs(int p){
	//모든 사람들이 이용할 계단을 선택한 경우, 이동을 시작한다
    if(p == people.size()){
        move_people();
        return;
    }
    //두 개의 계단 중 어느 것을 이용할지 정한다
    for(int s=0; s<2; s++){
        people[p].stair = s;
        //현재 사람의 위치에서 계단까지의 거리를 dis에 설정한다
        people[p].dis = abs(people[p].x - stairs[s].x) + abs(people[p].y - stairs[s].y);
        decide_stairs(p+1);
    }
}

int main(int argc, const char * argv[]) {
    int test_case;
    int T;
    cin >> T;
    
    for(test_case=1; test_case<=T; ++test_case){
    	//초기화
        stairs.clear();
        people.clear();
        min_time = -1;
        
        cin >> N;
        for(int y=0; y<N; y++){
            for(int x=0; x<N; x++){
                cin >> room[y][x];
                
                //사람이 있는 위치인 경우, people에 추가한다
                if(room[y][x] == 1){
                    person.stair = 0;
                    person.x = x;
                    person.y = y;
                    person.dis = 0;
                    person.move = 0;
                    people.push_back(person);
                }
                //계단인 경우, stairs에 추가한다
                else if(room[y][x] > 1){
                    stair.x = x;
                    stair.y = y;
                    stair.K = room[y][x];
                    stair.users.clear();
                    stairs.push_back(stair);
                }
            }
        }
        
        //사람들이 이용할 계단을 정한다
        decide_stairs(0);
        cout << "#" << test_case << " " << min_time << endl;
    }
    return 0;
}