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

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

코딩테스트 연습 - [PCCP 기출문제] 3번 / 충돌위험 찾기

제한사항

4. 다음 포인트로 이동할 때는 항상 최단 경로로 이동하며 최단 경로가 여러 가지일 경우, r 좌표가 변하는 이동을 c 좌표가 변하는 이동보다 먼저 합니다.

2 ≤ points의 길이 = n ≤ 100
    points[i]는 i + 1번 포인트의 [r 좌표, c 좌표]를 나타내는 길이가 2인 정수 배열입니다.
    1 ≤ r ≤ 100
    1 ≤ c ≤ 100
    같은 좌표에 여러 포인트가 존재하는 입력은 주어지지 않습니다.
2 ≤ routes의 길이 = 로봇의 수 = x ≤ 100
    2 ≤ routes[i]의 길이 = m ≤ 100
    routes[i]는 i + 1번째 로봇의 운송경로를 나타냅니다.
    routes[i]의 길이는 모두 같습니다.
    routes[i][j]는 i + 1번째 로봇이 j + 1번째로 방문하는 포인트 번호를 나타냅니다.
    같은 포인트를 연속으로 방문하는 입력은 주어지지 않습니다.
    1 ≤ routes[i][j] ≤ n

처음 문제를 접했을 때 맵이 나오고 최단 경로가 나오다 보니 다짜고짜 BFS를 생각했고 이는 문제를 어렵게 만들었음

• 장애물이 존재했다면 BFS가 맞았을지 몰라도 해당 문제의 경우 장애물이 존재하지 않기 때문에 BFS가 적절하지 않다고 생각됨

최초 BFS로 문제를 풀다가 경로는 찾았지만 시간초과가 생기는 테스트 케이스가 있어 다른 방식을 사용해야겠다고 생각이 듦

 

GPT에 문제 해설을 맡기고 확인하니 문제 설명에서 다음 포인트로 이동할 땐 Row먼저 이동하고 그다음 Col을 이동하는 조건이 있었음

 

이를 이용하면 목표지점까지 Row를 수정하면서 경로 저장 이후 목표지점 Col까지 수정하면서 경로 저장을 하면 쉽게 경로를 구할 수 있음

 

routes의 경우 최소 2개 이상이기 때문에 여러 point를 방문할 수 있어 여러 경로를 구하여 합쳐야 함. 합칠 때 point 시작 지점이 겹치기 때문에 첫 경로 이후에는 맨 앞 좌표를 빼고 저장

 

모든 경로를 구하면 각 스텝(시간)에 따라 로봇이 겹치는지 확인해야 하는데, 가장 처음에는 Set을 이용하여 set의 길이와 현재 동작하는 로봇 길이가 다르면 answer를 더해주었으나 동시에 여러 지점에서 발생할 경우에는 대처하지 못함

 

따라서 스텝에 따라 사용되는 좌표를 키로 저장하고 좌표에 존재하는 로봇의 수를 구해서 좌표에 하나 이상의 로봇이 있을 경우 answer을 더해주도록 함

 

가장 긴 경로를 기준으로 반복문을 수행해야 하기 때문에 구한 경로 배열을 length기준으로 sorting 하여 maxLength를 구함

const getPointRoute = (start, end) => {
    const [sr, sc] = start;
    const [er, ec] = end;
    
    const routes = [[sr, sc]];
    
    let curR = sr;
    let curC = sc;
    
    while(curR != er){
        if(sr > er){
            curR--;
        } else {
            curR++;
        }
        routes.push([curR, curC]);
    }
    
    while(curC != ec){
        if(sc > ec){
            curC--;
        } else {
            curC++;
        }
        routes.push([curR, curC]);
    }
    
    return routes;
}

function solution(points, routes) {
    var answer = 0;
    
    const paths = routes.map(route => {
        let start, end;
        let res = [];
        for(let i = 0; i < route.length; i++){
            if(i == 0) continue;
            start = route[i - 1];
            end = route[i];
            const path = getPointRoute(points[start - 1], points[end - 1]);
            if(res.length < 1){
                res.push(...path)    
            } else {
                res.push(...path.slice(1))
            }
        }
        
        return res;
    }).sort((a,b) => b.length - a.length);
    
    const maxLength = paths[0].length;
    
    for(let i = 0; i < maxLength; i++){
        const pointCnt = new Map();
        
        for(let path of paths){
            if(!path[i]) continue;
            const key = path[i].join();
            if(pointCnt.has(key)){
                const before = pointCnt.get(key);
                pointCnt.set(key, before + 1);
                continue;
            }
            pointCnt.set(key, 1);
        }
        
        pointCnt.forEach(cnt => {
            if(cnt > 1) answer++;
        })
    }
    
    return answer;
}