문제
어떤 물류 센터는 로봇을 이용한 자동 운송 시스템을 운영합니다. 운송 시스템이 작동하는 규칙은 다음과 같습니다.
물류 센터에는 (r, c)와 같이 2차원 좌표로 나타낼 수 있는 n개의 포인트가 존재합니다. 각 포인트는 1~n까지의 서로 다른 번호를 가집니다.
로봇마다 정해진 운송 경로가 존재합니다. 운송 경로는 m개의 포인트로 구성되고 로봇은 첫 포인트에서 시작해 할당된 포인트를 순서대로 방문합니다.
운송 시스템에 사용되는 로봇은 x대이고, 모든 로봇은 0초에 동시에 출발합니다. 로봇은 1초마다 r 좌표와 c 좌표 중 하나가 1만큼 감소하거나 증가한 좌표로 이동할 수 있습니다.
다음 포인트로 이동할 때는 항상 최단 경로로 이동하며 최단 경로가 여러 가지일 경우, r 좌표가 변하는 이동을 c 좌표가 변하는 이동보다 먼저 합니다.
마지막 포인트에 도착한 로봇은 운송을 마치고 물류 센터를 벗어납니다. 로봇이 물류 센터를 벗어나는 경로는 고려하지 않습니다.
이동 중 같은 좌표에 로봇이 2대 이상 모인다면 충돌할 가능성이 있는 위험 상황으로 판단합니다. 관리자인 당신은 현재 설정대로 로봇이 움직일 때 위험한 상황이 총 몇 번 일어나는지 알고 싶습니다. 만약 어떤 시간에 여러 좌표에서 위험 상황이 발생한다면 그 횟수를 모두 더합니다.
운송 포인트 n개의 좌표를 담은 2차원 정수 배열 points와 로봇 x대의 운송 경로를 담은 2차원 정수 배열 routes가 매개변수로 주어집니다. 이때 모든 로봇이 운송을 마칠 때까지 발생하는 위험한 상황의 횟수를 return 하도록 solution 함수를 완성해 주세요.
문제 정리
운송 로봇이 2차원 평명 위 여러 지점을 따라 이동한다.
각 로봇은 정해진 경로(routes)를 0초부터 동시에 출발하며,
이동 도중 같은 시간(t), 같은 위치(y, x)에 둘 이상의 로봇이 존재하면 이를 '충돌 위험'으로 판단한다.
목표 : 전체 이동 과정에서 발생하는 충돌 위험 횟수를 계산하는 것
1) points
- 운송지점들의 실제 좌표
- points[i] = [y, x]
points = [[3, 2], [6, 4], [4, 7], [1, 4]]→ 1번 포인트 = (3,2)
→ 2번 포인트 = (6,4)
→ 3번 포인트 = (4,7)
→ 4번 포인트 = (1,4)
2) routes
- 각 로봇이 방문해야할 포인트 번호들의 리스트
- routes[i] = [p1, p2, p3, ... ]
- i번 로봇은 p1 -> p2 -> p3 -> .. 순서로 이동
routes = [[4, 2], [1, 3], [4, 2], [4, 3]]→ 로봇 0: 4 → 2
→ 로봇 1: 1 → 3
→ 로봇 2: 4 → 2
→ 로봇 3: 4 → 3
3) 로봇 이동규칙
로봇은 1초당 1칸씩 움직인다.
- 규칙 1
- 행(y) 방향을 먼저 맞춘다.
- 목적지와 y가 다르면 y가 같아질 때까지 1초에 1칸씩 위 또는 아래로 이동- 그 다음 열(x) 방향을 이동한다.
- y가 같아진 이후는, x가 목적지와 같아질 때까지 1초에 1칸씩 왼쪽 또는 오른쪽 이동
- 출발 시점(t=0)에도 그 위치에 존재한다.
- 시작 위치 또한 충돌 체크 대상이다.
- 그 다음 열(x) 방향을 이동한다.
4) 충돌위험
같은 시간 t에 같은 좌표(y,x)에 두 대 이상의 로봇이 존재하면 충돌 위험이 1회 발생한다.
-> 시간 단위 별로 로봇들의 위치가 겹치는지 검사해야한다.
5) 충돌횟수 계산
1. 각 로봇의 전체 이동 경로를 시간순으로 생성한다.
- 시작점 포함
- 여러 구간(p->q->r)을 이어붙인다.
- 전체 로봇 중 가장 긴 이동시간 T를 구한다.
- t=0~T 까지:
- 해당 시점에 있는 좌표 세기
- count가 2 이상인 좌표의 계수 더하기
- 최종 합 = 충돌 위험 횟수
시뮬레이션 문제라고 볼 수 있겠다.
문제 해석
상당히 오래걸렸다....
중간에 길을 잃고 헤맨 문제다. 풀다가 길을 잃고 잃었다.
이 문제는 처음에 문제 정의를 단계적으로 해나가는게 중요한 것 같다. 무작정 구현하려고 하기보다는 전체적인 흐름과 틀을 명확히 하고 푸는게 시간 단축에 도움이 될 것이다.
필자는 pccp lv.2 를 갖고있는데 이 다음으로 넘어가기 위해서는 단련이 필요할 것 같다..
[정답 코드]
#include <string>
#include <vector>
#include <map>
using namespace std;
vector<vector<pair<int,int>>> mv; // mv[i][t] = i번 로봇이 t초에 있는 위치
// from → to 까지 y 먼저, 그 다음 x 방향으로 한 칸씩 이동 (시작점은 포함 X)
void move(int idx, const pair<int,int>& from, const pair<int,int>& to) {
int y = from.first;
int x = from.second;
int ty = to.first;
int tx = to.second;
// 1) y 방향 먼저 이동
while (y != ty) {
if (y < ty) y++; // 아래로
else y--; // 위로
mv[idx].push_back({y, x});
}
// 2) x 방향 이동
while (x != tx) {
if (x < tx) x++; // 오른쪽
else x--; // 왼쪽
mv[idx].push_back({y, x});
}
}
int solution(vector<vector<int>> points, vector<vector<int>> routes) {
int answer = 0;
// 포인트 번호 → 실제 좌표 (0-based)로 변환
vector<pair<int,int>> pos(points.size());
for (int i = 0; i < points.size(); i++) {
int y = points[i][0] - 1;
int x = points[i][1] - 1;
pos[i] = {y, x};
}
// 로봇 수만큼 mv 준비
mv.assign(routes.size(), {}); // resize + clear 역할
// 각 로봇별 전체 이동 경로 만들기
for (int i = 0; i < routes.size(); i++) {
// routes[i] = [p1, p2, p3, ...]
// p1 -> p2 -> p3 ... 순서로 이동
// 시작 포인트 (시간 0 위치)
int firstPointIdx = routes[i][0] - 1; // 포인트 번호 → 인덱스
mv[i].push_back(pos[firstPointIdx]); // t = 0 위치
// 각 구간 p[j] → p[j+1] 이동
for (int j = 0; j < routes[i].size() - 1; j++) {
int fromIdx = routes[i][j] - 1;
int toIdx = routes[i][j + 1] - 1;
move(i, pos[fromIdx], pos[toIdx]);
}
}
// 전체 시간 중 가장 긴 경로 길이 계산
int maxT = 0;
for (auto &path : mv) {
if ((int)path.size() > maxT) maxT = path.size();
}
// 시간 t별로, 같은 칸에 2대 이상 있는지 체크
for (int t = 0; t < maxT; t++) {
map<pair<int,int>, int> cnt; // 위치 → 몇 대의 로봇이 있는지
for (int r = 0; r < mv.size(); r++) {
if (t < mv[r].size()) { // 이 로봇이 t초에 아직 이동 중이면
cnt[mv[r][t]]++;
}
}
for (auto &p : cnt) {
if (p.second >= 2) answer++; // 같은 시간에 같은 칸에 2대 이상
}
}
return answer;
}
