[프로그래머스] [PCCP 기출문제] 3번 / 충돌위험 찾기 (js)

문제 설명 

어떤 물류 센터는 로봇을 이용한 자동 운송 시스템을 운영합니다. 운송 시스템이 작동하는 규칙은 다음과 같습니다.

1. 물류 센터에는 (r, c)와 같이 2차원 좌표로 나타낼 수 있는 n개의 포인트가 존재합니다. 각 포인트는 1~n까지의 서로 다른 번호를 가집니다.
2. 로봇마다 정해진 운송 경로가 존재합니다. 운송 경로는 m개의 포인트로 구성되고 로봇은 첫 포인트에서 시작해 할당된 포인트를 순서대로 방문합니다.
3. 운송 시스템에 사용되는 로봇은 x대이고, 모든 로봇은 0초에 동시에 출발합니다. 로봇은 1초마다 r 좌표와 c 좌표 중 하나가 1만큼 감소하거나 증가한 좌표로 이동할 수 있습니다.
4. 다음 포인트로 이동할 때는 항상 최단 경로로 이동하며 최단 경로가 여러 가지일 경우, r 좌표가 변하는 이동을 c 좌표가 변하는 이동보다 먼저 합니다.
5. 마지막 포인트에 도착한 로봇은 운송을 마치고 물류 센터를 벗어납니다. 로봇이 물류 센터를 벗어나는 경로는 고려하지 않습니다.

이동 중 같은 좌표에 로봇이 2대 이상 모인다면 충돌할 가능성이 있는 위험 상황으로 판단합니다. 관리자인 당신은 현재 설정대로 로봇이 움직일 때 위험한 상황이 총 몇 번 일어나는지 알고 싶습니다. 만약 어떤 시간에 여러 좌표에서 위험 상황이 발생한다면 그 횟수를 모두 더합니다.

운송 포인트 n개의 좌표를 담은 2차원 정수 배열 points와 로봇 x대의 운송 경로를 담은 2차원 정수 배열 routes가 매개변수로 주어집니다. 이때 모든 로봇이 운송을 마칠 때까지 발생하는 위험한 상황의 횟수를 return 하도록 solution 함수를 완성해 주세요.

 

제한사항

• 2 ≤ points의 길이 = n ≤ 100
• 2 ≤ routes의 길이 = 로봇의 수 = x ≤ 100

 

입출력 예

points	routes	result
[[3, 2], [6, 4], [4, 7], [1, 4]]	[[4, 2], [1, 3], [2, 4]]	1
[[3, 2], [6, 4], [4, 7], [1, 4]]	[[4, 2], [1, 3], [4, 2], [4, 3]]	9
[[2, 2], [2, 3], [2, 7], [6, 6], [5, 2]]	[[2, 3, 4, 5], [1, 3, 4, 5]]	0

입출력 예 설명

입출력 예 #1

그림처럼 로봇들이 움직입니다. 3초가 지났을 때 1번 로봇과 2번 로봇이 (4, 4)에서 충돌할 위험이 있습니다. 따라서 1을 return 해야 합니다.

입출력 예 #2

 

그림처럼 로봇들이 움직입니다. 1, 3, 4번 로봇의 경로가 같아 이동하는 0 ~ 2초 내내 충돌 위험이 존재합니다. 3초에는 1, 2, 3, 4번 로봇이 모두 (4, 4)를 지나지만 위험 상황은 한 번만 발생합니다.

4 ~ 5초에는 1, 3번과 2, 4번 로봇의 경로가 각각 같아 위험 상황이 매 초 2번씩 발생합니다. 6초에 2, 4번 로봇의 충돌 위험이 발생합니다. 따라서 9를 return 해야 합니다.

입출력 예 #3

그림처럼 로봇들이 움직입니다. 두 로봇의 경로는 같지만 한 칸 간격으로 움직이고 2번 로봇이 5번 포인트에 도착할 때 1번 로봇은 운송을 완료하고 센터를 벗어나 충돌 위험이 없습니다. 따라서 0을 return 해야 합니다.

 

나의 풀이 (실패한 풀이 ) 

function solution(points, routes) {
    const dx = [-1, 1, 0, 0];
    const dy = [0, 0, -1, 1];

    let maxX = 0, maxY = 0;

    points.forEach(([x, y]) => {
        maxX = Math.max(maxX, x);
        maxY = Math.max(maxY, y);
    });

    // BFS를 사용해 경로를 계산
    const directions = (startX, startY, targetX, targetY) => {
        const queue = [[startX, startY, [[startX, startY]]]]; // 시작 위치 포함
        const visited = Array.from({ length: maxX + 1 }, () => Array(maxY + 1).fill(false));
        visited[startX][startY] = true;

        while (queue.length > 0) {
            const [x, y, path] = queue.shift();

            // 목표 위치에 도달하면 경로 반환
            if (x === targetX && y === targetY) return path;

            for (let i = 0; i < 4; i++) {
                const nx = x + dx[i];
                const ny = y + dy[i];

                if (
                    nx >= 0 && nx <= maxX && ny >= 0 && ny <= maxY &&
                    !visited[nx][ny]
                ) {
                    visited[nx][ny] = true;
                    queue.push([nx, ny, [...path, [nx, ny]]]);
                }
            }
        }

        return []; // 목표에 도달할 수 없는 경우 빈 배열 반환
    };

    const paths = routes.map(([start, end]) => {
        const [startX, startY] = points[start - 1];
        const [endX, endY] = points[end - 1];
        return directions(startX, startY, endX, endY);
    });

    let collisionCount = 0;
    const robotPositions = Array(routes.length).fill(0); // 각 로봇의 현재 경로 인덱스

    while (true) {
        const positionMap = new Map();
        let activeRobots = 0;

        for (let i = 0; i < paths.length; i++) {
            if (robotPositions[i] < paths[i].length) {
                const [x, y] = paths[i][robotPositions[i]];
                const key = `${x},${y}`;

                positionMap.set(key, (positionMap.get(key) || 0) + 1);
                robotPositions[i]++;
                activeRobots++;
            }
        }

        positionMap.forEach((count) => {
            if (count > 1) collisionCount++;
        });

        if (activeRobots === 0) break; // 모든 로봇이 도착한 경우 종료
    }

    return collisionCount;
}

bfs 함수를 따로 만들어서 최단거리에 이동하는 좌표를 저장하고 각 시간마다 충돌했는지 검사하도록 구현했는데 테스트 케이스는 통과했지만 제출을 했을 때 20점이 나와버린다 ... 

 

나의 풀이 (통과한 풀이)

 

function solution(points, routes) {
    function getPath(startX, startY, targetX, targetY) {
        const path = [[startX, startY]];
        let x = startX;
        let y = startY;

        // 먼저 x 좌표를 목표 지점까지 이동
        while (x !== targetX) {
            if (x < targetX) {
                x++;
            } else {
                x--;
            }
            path.push([x, y]);
        }

        // 그 다음 y 좌표를 목표 지점까지 이동
        while (y !== targetY) {
            if (y < targetY) {
                y++;
            } else {
                y--;
            }
            path.push([x, y]);
        }

        return path;
    }
    
    const paths = routes.map(route => {
        let fullPath = [];
        for (let i = 0; i < route.length - 1; i++) {
            const [startX, startY] = points[route[i] - 1];
            const [endX, endY] = points[route[i + 1] - 1];
            const subPath = getPath(startX, startY, endX, endY);
            fullPath = fullPath.concat(subPath.slice(fullPath.length ? 1 : 0));
        }
        return fullPath;
    });
   
    let collisionCount = 0;

    // 모든 로봇을 동기적으로 이동하며 충돌 계산
    while (paths.some(path => path.length > 0)) {
        const positionMap = new Map();

        paths.forEach(path => {
            if (path.length > 0) {
                const [x, y] = path.shift();
                const key = `${x},${y}`;
                positionMap.set(key, (positionMap.get(key) || 0) + 1);
            }
        });

        // 충돌 계산 (한 위치에서 여러 로봇이 모이면 한 번만 카운트)
        positionMap.forEach(count => {
            if (count > 1) {
                collisionCount++;
            }
        });
    }

    return collisionCount;
}

 

여러 서치를 해본 결과 문제에서 주어진 조건을 활용하여 x 좌표를 우선적으로 이동하는 방식으로 최단 경로를 간단하게 구하는 방식으로 변경하니 제출을 성공하였다 !! 장애물이 존재한다면 이렇게 하면 안되지만 문제에서는 장애물이 없기 때문에 가능한 방법이었다..  맨날 기존에 풀던 방식대로만 생각하고 문제를 접한것 같아서 아쉽다 ..

fullPath = fullPath.concat(subPath.slice(fullPath.length ? 1 : 0)); 
이 부분은 만약에 경로가 4->2 ->1 이런식으로 여러 포인트를 거쳐서 간다면 각 경로를 연결할 때 중복을 제거하기 위함이다. 

충돌 탐지 방법은 도저히 생각나지 않아 지느님의 도움을 받았다.. 이문제는 꼭 다시한번 풀어봐야겠다고 생각했다.