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

프로그래머스

N개의 포인트가 있고 해당 포인트들을 이동하는 로봇이 있을 때, 로봇들이 이동 중 같은 좌표에 2대 이상 모이는 상황이 몇번 발생하는지 구해주세요. (모든 경로는 최단 경로이며 Y좌표가 X좌표보다 우선순위가 높습니다)

 

 

풀이방법

동서남북 모든 방향으로 갈 수 있으며, Y좌표가 X좌표보다 우선순위가 높기 때문에

시작 좌표와 종료 좌표를 안다면 경로를 파악할 수 있습니다.

Y좌표부터 목표 좌표에 맞추고, X좌표를 목표 좌표에 맞추면 됩니다.

그리고 시간의 흐름에 따라 이동한 경로를 기록해주면 됩니다.

 

map<pair<int, pair<int, int>>, int> logs;

 

저는 Map을 사용하여 풀이하였으며 시간과 위치값을 키로, 로봇 수를 값으로 설정하였습니다.

 

if (logs.find(key) != logs.end())
    logs[key]++;
else
    logs.insert({key, 1});

모든 로봇을 시간의 흐름에 따라 이동시키면서 logs에 기록했습니다.

 

int answer = 0;
for (auto& log : logs)
{
    int cnt = log.second;
    if (cnt > 1){
        answer++;     
    }
}

모든 기록을 순회하며 로봇의 수가 1보다 크다면 answer을 업데이트해주는 방식으로 문제를 해결했습니다.

 

 

정답 코드

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

using namespace std;

map<pair<int, pair<int, int>>, int> logs;
void update(pair<int, pair<int, int>> key)
{
    if (logs.find(key) != logs.end())
        logs[key]++;
    else
        logs.insert({key, 1});
}

int solution(vector<vector<int>> points, vector<vector<int>> routes) 
{
    for (auto& route : routes)
    {
        int time = 0;
        for (int j = 0; j < route.size()-1; j++)
        {
            int start = route[j]-1;
            int dest = route[j+1]-1;
   
            int y = points[start][0];
            int x = points[start][1];
            
            int dirY = points[dest][0] - y > 0 ? 1 : -1;
            int dirX = points[dest][1] - x > 0 ? 1 : -1;
            
            if (j == 0)
                update({time++, {y, x}});
            
            while (y != points[dest][0])
            {
                y += dirY;
                update({time++, {y, x}});
            }
            
            while (x != points[dest][1])
            {
                x += dirX;
                update({time++, {y, x}});
            }
        }
    }

    int answer = 0;
    for (auto& log : logs)
    {
        int cnt = log.second;
        if (cnt > 1){
            answer++;     
        }
    }
    
    return answer;
}