프로그래머스 문제 - 충돌위험 찾기

프로그래머스 충돌위험 찾기 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

어떤 물류 센터에서 로봇을 이용한 자동 운송 시스템을 운영합니다.
1. 물류 센터에는 (r, c)와 같이 2차원 좌표로 나타낼 수 있는 n개의 포인트가 존재합니다. 각 포인트는 1~n까지의 서로 다른 번호를 가집니다.
2. 로봇마다 정해진 운송 경로가 존재합니다. 운송 경로는 m개의 포인트로 구성되고 로봇은 첫 포인트에서 시작해 할당된 포인트를 순서대로 방문합니다.
3. 운송 시스템에 사용되는 로봇은 x대이고, 모든 로봇은 0초에 동시에 출발합니다. 로봇은 1초마다 r 좌표와 c 좌표 중 하나가 1만큼 감소하거나 증가한 좌표로 이동할 수 있습니다.
4. 다음 포인트로 이동할 때는 항상 최단 경로로 이동하며 최단 경로가 여러 가지일 경우, r 좌표가 변하는 이동을 c 좌표가 변하는 이동보다 먼저 합니다.
5. 마지막 포인트에 도착한 로봇은 운송을 마치고 물류 센터를 벗어납니다. 로봇이 물류 센터를 벗어나는 경로는 고려하지 않습니다.
이동 중 같은 좌표에 로봇이 2대 이상 모인다면 충돌할 가능성이 있는 위첨 상황으로 판단합니다.
이때, 위험한 상황이 총 몇 번 일어나는지 구해야합니다.

문제 풀이

각 로봇들이 움직이는 최단 경로를 세로부터 움직이도록 하여 모두 계산해줍니다.
이후 계산된 경로를 각각 비교하여 같은 시간때에 같은 좌표에 존재하는 여러 로봇들을 검사해줍니다.
주의해야 할 점은 한번에 한 점에서 로봇이 수십대가 부딪혀도 위험한 상황은 1번으로 계산됩니다. 또한 같은 시간때에 각각 다른 좌표에서 위험한 상황이 일어났을 경우, 이는 각 좌표에서 위험한 상황이 생긴 수 만큼 계산해줍니다.
모든 로봇의 경로가 끝날 때까지 계산해준 후 나온 총 위험한 상황을 출력해주면 됩니다.

시간초과가 생기지 않도록 이미 위험한 상황이나, 경로가 끝난 로봇들은 계산에서 제외시켜 주었습니다.

전체 코드

#include <bits/stdc++.h>
#include <string>
#include <vector>

using namespace std;

int solution(vector<vector<int>> points, vector<vector<int>> routes) {
    int answer = 0;
    
    vector<vector<pair<int, int>>> robotRoutes(101, vector<pair<int, int>>());
    
    pair<int, int> p;
    int num = 0, maxLength = 0;
    
    //로봇들의 경로 저장
    for(int i = 0; i < routes.size(); i++)
    {
        for(int j = 1; j < routes[i].size(); j++)
        {
            int start = routes[i][j-1];
            int end = routes[i][j];
            p = make_pair(points[start-1][0], points[start-1][1]);

            while(points[end-1][0] != p.first)
            {
                robotRoutes[num].push_back(p);
                points[end-1][0] > p.first ? p.first++ : p.first--;
            }
            while(points[end-1][1] != p.second)
            {
                robotRoutes[num].push_back(p);
                points[end-1][1] > p.second ? p.second++ : p.second--;
            }      
        }
        robotRoutes[num].push_back(p);
        
        if(maxLength < robotRoutes[num].size())
            maxLength = robotRoutes[num].size();
        
        num++;
    }
    
    int routeSize = routes.size();
    pair<int, int> currentPoint;
    
    //충돌 상황 체크
    for(int index = 0; index < maxLength; index++)
    {
        for(int i = 0; i < routeSize; i++)
        {
            if(robotRoutes[i].size() <= index)
                continue;
            
            if(robotRoutes[i][index].first == -1)
                continue;
            
            currentPoint = robotRoutes[i][index];
            for(int j = i+1; j < routeSize; j++)
            {
                if(robotRoutes[j].size() <= index)
                    continue;
            
                if(robotRoutes[j][index].first == -1)
                    continue;
                
                if(currentPoint == robotRoutes[j][index])
                {
                    if(robotRoutes[i][index].first != -1)
                        robotRoutes[i][index] = make_pair(-1, -1);
                    
                    robotRoutes[j][index] = make_pair(-1, -1);
                }
            }
            //만약 중복되는 포인트가 한개라도 있었을 때 휫수 추가
            if(robotRoutes[i][index].first == -1)
            {
                answer++;
            }
        }
    }
    
    return answer;
}

출저

https://school.programmers.co.kr/learn/courses/30/lessons/340211