※ 출처 : 프로그래머스>PCCP 기출 LV2. 충돌 위험 찾기
1. 문제 개요
1) 문제 설명
- (r,c) 좌표 (r: x좌표, c: y좌표)
- 로봇마다 다음 포인트로 이동 시 최단 경로를 잡을 때, 행(위아래) 이동을 먼저 수행 -> 열(좌우)이동
- 동일 좌표에 로봇이 2대 이상인 경우 => ★충돌 위험 상황★
- (문제) 로봇이 운송을 마칠떄까지 발생하는 "충돌 위험 횟수"를 계산하여 반환
2) 입출력 형식
- (입력) points : 운송 포인트(n개)의 좌표를 담은 2차원 정수 배열
- (입력) routes : 로봇 x대의 운송 경로를 담은 2차원 정수 배열
- (출력) return val : 충돌 위험 횟수 (int)
3) 제한 사항
- 모든 로봇은 routes[i]의 길이 만큼 움직이며, 더 혹은 덜 움직이는 로봇은 존재하지 않는 아주 심플한 케이스로 한정!
1. Solution I
1) MAP을 활용한 구현
핵심 로직
1. 로봇 이동 경로 계산:
-
각 로봇이 routes에 정의된 지점 간의 경로를 계산하여 route에 저장
-
경로 계산은 다음과 같이 이루어집니다:
x축과 y축을 각각 따로 고려하여, 한 방향으로 먼저 움직인 후 다음 방향으로 움직입니다.
2. 경로 충돌 검사:
-
모든 로봇의 경로가 계산된 후, 가장 많이 움직인 로봇의 최대 경로 길이를 기준으로 각 시간마다 각 좌표에서 몇 대의 로봇이 존재하는지 카운트
-
동일한 좌표에 여러 로봇이 있는 경우, 즉 두 로봇 이상이 같은 위치에 있다면 answer 값 증가
#include <string>
#include <vector>
#include <map>
#include <iostream>
using namespace std;
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
//! r행(위아래)로 먼저 움직이고, c열(좌우)로 움직임
// 로봇 별 이동 경로
map<int, vector<pair<int, int>>> route;
int solution(vector<vector<int>> points, vector<vector<int>> routes)
{
int answer = 0;
int x = routes.size(); // 로봇 개수
int move_cnt = routes[0].size(); // 포인트 이동 횟수
for (int i = 0;i < x;i++)
{
int n = 0;
vector<pair<int, int>> r;
for (int j = 0;j < move_cnt - 1;j++)
{
// 지점에서 다른 지점 갈때 다시 출발하면 안됨.
int before_x = points[routes[i][j] - 1][0];
int before_y = points[routes[i][j] - 1][1];
int next_x = points[routes[i][j + 1] - 1][0];
int next_y = points[routes[i][j + 1] - 1][1];
int k = before_x;
int l = before_y;
// 아래로
if (before_x < next_x)
{
if (j != 0) k++;
for (;k <= next_x;)
r.push_back({ k++,before_y });
k -= 1;
// 우로 이동
if (before_y < next_y)
{
l += 1;
for (;l <= next_y;l++)
r.push_back({ k,l });
}
// 좌로 이동
else if (before_y > next_y)
{
l -= 1;
for (;l >= next_y;l--)
r.push_back({ k,l });
}
}
// 위로
else if (before_x > next_x)
{
if (j != 0)
k--;
for (;k >= next_x;)
r.push_back({ k--,before_y });
k += 1;
// 우로 이동
if (before_y < next_y)
{
l += 1;
for (;l <= next_y;l++)
r.push_back({ k,l });
}// 좌로 이동
else if (before_y > next_y)
{
l -= 1;
for (;l >= next_y;l--)
r.push_back({ k,l });
}
}
else
{
// 우로만
if (before_y < next_y)
{
if (j != 0) l++;
for (;l <= next_y;l++)
r.push_back({ k,l });
}
else // 좌로만
{
if (j != 0) i--;
for (;l >= next_y;l--)
r.push_back({ k,l });
}
}
}
route.insert({ i + 1,r });
}
// 1,2,... n번째 로봇까지의 경로 : r (vector<pair<int,int>>)
int max_len = 0;
for (int i = 0;i < x;i++)
if (max_len < route[i + 1].size())
max_len = route[i + 1].size();
// 최대 좌표 이동 횟수
for (int k = 0;k < max_len;k++)
{
// 로봇의 수 (좌표 출현 갯수) -> second(int)의 값이>1인 경우 answer++;
map<pair<int, int>, int> loc_cnt;
for (int a = 0;a < x;a++)
if (route[a + 1].size() > k)
loc_cnt[{route[a + 1][k].first, route[a + 1][k].second}]++;
for (auto iter = loc_cnt.begin();iter != loc_cnt.end();iter++)
if (iter->second > 1) answer++;
}
return answer;
}반복문과 조건문의 향연... ->
결론 !
이 소스는 답이 없다. 다시해라 ㅠㅠㅠㅠㅠㅠ힝....
Solution 2.
#include <string>
#include <vector>
#include <map>
#include <iostream>
using namespace std;
int solution(vector<vector<int>> points, vector<vector<int>> routes)
{
int answer = 0;
// x : 로봇의 수
int x = routes.size();
// move_cnt : 포인트 이동 횟수
int move_cnt = routes[0].size();
map<int, vector<pair<int, int>>> route;
// x개의 로봇이 돌아다님
for (int i = 0;i < x;i++)
{
// i+1번째 로봇의 이동 경로
vector<int> r = routes[i];
vector<pair<int, int>> rtmp;
// r : {4,2}
for (int z = 0;z < r.size() - 1;z++)
{
int before_x = points[r[z] - 1][0];
int before_y = points[r[z] - 1][1];
int next_x = points[r[z + 1] - 1][0];
int next_y = points[r[z + 1] - 1][1];
// 처음에만 시작 위치 포함
if (z == 0)
rtmp.push_back({ before_x,before_y });
int k = before_x;
int l = before_y;
if (before_x < next_x) // 아래로
{
k += 1;
for (;k <= next_x;k++)
rtmp.push_back({ k,before_y });
}
else if (before_x > next_x) // 위로
{
k -= 1;
for (;k >= next_x;k--)
rtmp.push_back({ k,before_y });
}
if (before_y < next_y) // 우로만
{
l += 1;
for (;l <= next_y;l++)
rtmp.push_back({ next_x,l });
}
else if (before_y > next_y) // 좌로만
{
l -= 1;
for (;l >= next_y;l--)
rtmp.push_back({ next_x,l });
}
}
route[i + 1] = rtmp;
}
int max_len = 0;
for (int i = 0;i < x;i++)
if (max_len < route[i + 1].size())
max_len = route[i + 1].size();
// 최대 좌표 이동 횟수
for (int k = 0;k < max_len;k++)
{
// 로봇의 수 (좌표 출현 갯수) -> second(int)의 값이>1인 경우 answer++;
map<pair<int, int>, int> loc_cnt;
for (int a = 0;a < x;a++)
if (route[a + 1].size() > k)
loc_cnt[{route[a + 1][k].first, route[a + 1][k].second}]++;
for (auto iter = loc_cnt.begin();iter != loc_cnt.end();iter++)
if (iter->second > 1) answer++;
}
return answer;
}굳이 상하 -> 좌우 를 중첩 조건문으로 풀어내지 않고, 순차로 처리하도록 하였다. 그리고 else 가 아니라 else if 로 이동하지 않는 경우에 대해서는 배제한다. 그 뒤에 최대 좌표 이동 횟수를 계산하는 로직을 기존과 동일
3. 코드 실행 결과 (성공♣)
