[프로그래머스] 충돌위험 찾기 (C++)

문제

프로그래머스

풀이

이 문제는 물류 센터의 로봇 자동 운송 시스템을 시뮬레이션하는 문제이다.

1. 물류 센터에는 2차원 좌표로 표현되는 n개의 포인트가 있다.
2. x대의 로봇이 있으며, 각 로봇은 정해진 경로를 따라 포인트를 순서대로 방문한다.
3. 모든 로봇은 동시에 출발하며, 1초에 한 칸씩 이동한다. 이동 시 최단 경로를 선택한다.
4. 로봇은 r 좌표 변화를 c 좌표 변화보다 우선시한다.
5. 두 대 이상의 로봇이 같은 좌표에 있을 때 "위험 상황"으로 간주한다.
6. 목표는 모든 로봇이 운송을 마칠 때까지 발생하는 총 위험 상황의 횟수를 계산하는 것이다.

입력으로는 포인트의 좌표(points)와 각 로봇의 운송 경로(routes)가 주어지고, 매 시간마다 로봇들의 위치를 추적하여  위험 상황 횟수를 반환해야한다.

 

접근 방법

1. vector로 로봇의 경로를 초기화
2. queue로 시뮬레이션 순서를 관리
3. map으로 각 좌표의 로봇 수를 추적

#include <string>
#include <vector>
#include<queue>
#include<map>

using namespace std;

map<pair<int,int>, int> robotMap;

int GetDir(int cur, int goal){
    return cur < goal ? 1 : -1;  
}

int GetAnswer(){
    int answer = 0;
    for(auto it = robotMap.begin(); it != robotMap.end(); it++){
        if(it->second > 1){
            answer++;
        }
    }
    return answer;
}

int solution(vector<vector<int>> points, vector<vector<int>> routes) {
    int answer = 0;
    
    vector<vector<pair<int,int>>> move;
    queue<pair<pair<int,int>,pair<int,int>>> q;
    
    // 초기화
    for(int i = 0; i < routes.size(); i++){
        vector<pair<int,int>> temp;
        for(int j = 0; j < routes[i].size(); j++){
            if(j == 0){ // 시작 좌표
            	// {{로봇의 번호, 다음 목적지 번호}, {현재 좌표}}
                q.push({{i , 1}, {points[routes[i][j] - 1][0],  points[routes[i][j] - 1][1]}});
            }
            temp.push_back({points[routes[i][j] - 1][0], points[routes[i][j] - 1][1]});
        }
        move.push_back(temp);
    }
    
    // 첫 좌표가 같을 경우 판별
    for(int i = 0; i < move.size(); i++){
        robotMap[{move[i][0].first, move[i][0].second}]++;
    }
    answer += GetAnswer();
    
    // 시뮬레이션 시작
    while(!q.empty()){
        robotMap.clear();
        int size = q.size();
        
        for(int i = 0; i <size; i++){
            int robotNum = q.front().first.first;
            int curArriveNum = q.front().first.second;
            pair<int, int> curPos=  q.front().second;
            pair<int,int> goal = move[robotNum][curArriveNum];
            
            q.pop();
            
            if(curPos.first != goal.first){
                curPos.first += GetDir(curPos.first, goal.first);
            }
            else{
                curPos.second += GetDir(curPos.second, goal.second);
            }
            robotMap[curPos] ++;
            if(curPos.first == goal.first && curPos.second == goal.second){
   
                 if(curArriveNum < move[robotNum].size() - 1){
                    curArriveNum++;
                    q.push({{robotNum, curArriveNum},{curPos}});         
                }
            }
            else{
                q.push({{robotNum, curArriveNum},{curPos}});
            }
        }
        
         answer += GetAnswer();
    }
    
    return answer;
}

---