[프로그래머스] Level 2 : 충돌위험 찾기

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

프로그래머스

 

0초에도 충돌위험 처리를 해줘야 한다.

따라서 반복 전에 0초 충돌위험 처리를 따로 해줬다.

 

1초~ 부터는 각 로봇들의 다음 이동 위치를 Map에 담고, 중복되면 충돌위험을 1 올리고 해당 위치는 충돌위험 처리를 못하도록 한다.

모든 운송지에 도착한 로봇은 위치를 -1로 초기화하고, 총 로봇의 수를 1 줄인다.

 

운송지 순회는 {  1, 4, 2, 3 } 순으로 경유한다고 하면, 1은 0초 즉, 시작할 때 이동하므로 제외하고 4부터 이동하여 도착하면 -1로 초기화한다. { 1, -1, 2, 3 }

이렇게 모든 운송지를 -1로 초기화하면, 운송지 조회 반복문에서 false로 벗어나기 떄문에 로봇 제거 로직을 수행한다.

#include <string>
#include <vector>
#include <map>
using namespace std;

int solution(vector<vector<int>> points, vector<vector<int>> routes) {
	int answer = 0, Robot = routes.size();

	vector<pair<int, int>> Pos(routes.size() + 1);
	map<pair<int, int>, pair<int, bool>> s;

	// 0초
	for (int i = 0; i < routes.size(); ++i)
	{
		int y = points[routes[i][0] - 1][0], x = points[routes[i][0] - 1][1];
		Pos[i + 1] = { y, x };
		s[{y, x}].first++;
		if (s[{y, x}].first == 1) s[{y, x}].second = false;
		if (s[{y, x}].first > 1 && !s[{y, x}].second) answer++, s[{y, x}].second = true;
	}

	// 1초~
	while (Robot > 0)
	{
		s.clear();
		for (int i = 0; i < routes.size(); ++i) // 각 로봇 순회
		{
			int& y = Pos[i + 1].first, & x = Pos[i + 1].second; // 현재 로봇의 위치
			if (y == -1) continue; // 배송을 마친 로봇인 경우 제외

			bool Check = false;
			for (int j = 1; j < routes[i].size(); ++j) // 각 로봇의 배송 경로 순회
			{
				if (routes[i][j] != -1) // 이미 배송한 배송지인 경우 제외
				{
					Check = true;
					int ny = points[routes[i][j] - 1][0], nx = points[routes[i][j] - 1][1]; // 목표 배송지 위치

					// 최단경로 이동
					if (y == ny) x > nx ? x-- : x++;
					else y > ny ? y-- : y++;

					s[{y, x}].first++; // 이동한 위치 +1
					if (s[{y, x}].first == 1) s[{y, x}].second = false; // 처음 로봇이 도착한 위치인 경우 미충돌 표시
					if (s[{y, x}].first > 1 && !s[{y, x}].second) answer++, s[{y, x}].second = true; // 이동한 위치에 다른 로봇이 있고, 미충돌인 경우 충돌 +1, 충돌 표시

					if (y == ny && x == nx) routes[i][j] = -1; // 현재 배송지 배송 완료
					break;
				}
			}
			if (!Check) y = -1, Robot--; // 배송지가 없는 경우 로봇 제거
		}
	}
	return answer;
}