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

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

using namespace std;

map<pair<int, pair<int,int>>, int>m; //특정 시간에 특정 위치를 지난 사람 카운트


int solution(vector<vector<int>> points, vector<vector<int>> routes) {
    int answer = 0;
    
    for(auto route : routes)
    {
        int time = 0;
        for(int i=0; i<route.size()-1; i++)
        {
            int s = route[i]-1; //0 베이스 인덱스
            int e = route[i+1]-1;
            
            int x = points[s][0]; //출발점
            int y = points[s][1];
            
            if(i==0) m[{time++, {x, y}}]++;; //첫 포인트
            
            while(x!=points[e][0]) //한칸씩 이동
            {
                x += points[e][0] - x > 0 ? 1 : -1; 
                m[{time++, {x, y}}]++;
            }
            
            while(y!=points[e][1])
            {
                y += points[e][1] - y > 0 ? 1 : -1;
                m[{time++, {x, y}}]++;
            } 
        }
    }
    
    for(auto i : m)
    {
        if(i.second > 1) answer++; //충돌 체크
    }
    
    return answer;
}

 

특정 시간에 특정 위치를 지난 사람을 카운트하기 위해 map을 사용한다.

먼저 route에 대해 0 베이스 인덱스로 값을 수정해준다.

route 시작점을 기준으로 points에서 출발점에 대한 x, y 좌표를 구해준다.

 

먼저 첫 포인트의 경우는 (0, 0)에서 바로 출발하므로 첫 시간 대해 대한 좌표를 바로 설정해준다. (출발점이 도착점)

 

다음으로는 r 좌표와 c 좌표 중 하나가 감소하거나 증가한 좌표로 이동시키는 것이다.

x좌표와 y좌표 둘다 도착점에 도착할 때까지 1 또는 -1을 주며 한칸씩 이동하며, 그에 따라 증가한 시간과 해당 시간의 좌표를 map에 담아 개수를 카운팅한다.

 

방향의 경우 도착점과 현재 x 값의 차이를 통해 1인지 -1인지 알 수 있다.

만약 차이값이 0 보다 크다면, x의 경우 오른쪽으로 이동해야 한다는 것이기에 1인 것을 알 수 있다.

만약 차이값이 0 보다 작다면, x의 경우 왼쪽으로 이동해야한다는 것이기에 -1인 것을 알 수 있다.

y 경우도 마찬가지로 삼항연산자를 통해 간단히 체크가 가능하다.

 

이때 주의할점은 문제에 주어진 조건에 따라 r 좌표가 변하는 이동을 c 좌표가 변하는 이동보다 먼저 하는 것이다. (순서)

이후에는 이미 카운팅 된 값에 대해 1보다 크다면 충돌이 일어났다는 것이기에 해당 경우만 체하여 출력해주면 된다.