[프로그래머스 Lv2] 충돌 위험 찾기 - Javascript 풀이

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

프로그래머스

---

문제

로봇들이 동시에 이동할때 충돌 위험 상황의 개수를 찾는 문제

 

생각

처음에 좌표 중심으로 문제를 풀었다.

각 로봇이 이동하는 동안 방문한 좌표들을 기록하고,

후에 같은 좌표에 도착한 시간이 겹치는지 확인하는 방식으로 풀었다.

해당 풀이의 문제점은 충돌의 기준을 좌표 중심으로만 봤다는 점이다. 

시간 축이 전역적으로 맞춰지지 않은 것이 한계점이었다.

 

문제를 풀기 위해선,

같은 시간대의 로봇들의 상태에 대해 봐야한다는 것을 깨달았다.

 

★ 공간 중심의 사고 → 시간 중심의 사고

 

문제풀이

같은 시간에 같은 좌표에 도달한 경우를 세면 충돌 위험을 계산할 수 있다.

 

Map 자료 구조를 사용한다.

key:  'r, c, time' 

vaule: 해당 좌표를 그 시간에 방문한 로봇 수

 

모든 로봇의 경로를 순회하면서,

현재 좌표에서 목표 좌표까지 한칸 씩 이동한다.

이동할 때마다 vis에 'r, c, time'을 기록한다.

이때, 꼭 마지막 도착 좌표도 기록해줘야 한다.

 

모든 로봇이 이동완료한 후,

vis의 vaule 중 값이 2 이상인 경우를 카운트하여 반환한다.

 

시간 복잡도는 

좌표당 각 1번 기록이므로,

각 로봇의 이동 경로 길이 x 로봇 수

= 10,000 x 100 = 1000,000 → O(NxM) 이다.

 

코드

function solution(points, routes) {
  const n = points.length;
  const vis = new Map(); // 'r,c,time' 조합을 key로 사용

  for (let idx = 0; idx < routes.length; idx++) {
    const route = routes[idx];
    let time = 0;

    for (let i = 0; i < route.length - 1; i++) {
      let [r, c] = points[route[i] - 1];
      const [er, ec] = points[route[i + 1] - 1];

      // r 방향 이동
      while (r !== er) {
        const key = `${r},${c},${time}`;
        vis.set(key, (vis.get(key) || 0) + 1);
        r += r < er ? 1 : -1;
        time++;
      }

      // c 방향 이동
      while (c !== ec) {
        const key = `${r},${c},${time}`;
        vis.set(key, (vis.get(key) || 0) + 1);
        c += c < ec ? 1 : -1;
        time++;
      }
    }

    // 마지막 위치도 기록 (멈춘 자리)
    const key = `${er},${ec},${time}`;
    vis.set(key, (vis.get(key) || 0) + 1);
  }

  // 한 시각(t)에 같은 좌표(r,c)에 로봇 ≥ 2 → 충돌 위험
  let result = 0;
  for (const v of vis.values()) {
    if (v >= 2) result++;
  }

  return result;
}