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

문제 - 충돌위험 찾기(Level 2)

---

문제 설명

 

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

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 함수를 완성해 주세요.

 

 

간단하게 문제 설명하면 

• 포인트는 위의 1, 2, 3, 4와 같이 시작 포인트를 말하고, 이는 points 배열 순서대로의 값을 말하는데, 위로 예시를 들면 points = [[3, 2], [6, 4], [4, 7], [1, 4]] 라고 했을 때, [3, 2]는 1번 포인트, [6, 4]가 2번 포인트를 말한다
• 운송 경로(routes)도 예시로 보면 쉬운데, routes = [[4, 2], [1, 3], [2, 4]] 라고 했을 때, 첫 번째 운송 경로는 4번 포인트가 2번으로 가야 하고, 두 번째는 1번 포인트는 3번으로, 세 번째는 2번은 4번으로 가야한다는 것을 뜻한다
• 각 운송 경로의 포인트를 이동시킬 때(ex. 4 -> 2) 최단 거리로 이동시켜야 하며, 최단 거리가 여러 개인 경우는 움직이는 방향을 위, 아래 -> 오른쪽, 왼쪽 순으로 이동시켜야 한다
• 우리가 구해야 하는 값은 먼저 각 운송 경로(routes)의 경로? 4 -> 2면 4번 포인트부터 2번 포인트까지의 경로 값(좌표)을 구하고, 구한 경로 값들을 시작 점부터 끝 점까지 동시에 이동시키면서 충돌하는 총 횟수를 구하면 된다

실수했던 점은 최단 경로를 구해야 한다는 생각이 들자마자 BFS를 이용해서 찾았는데, 생각해보니 이 문제를 그럴 필요가 없다. 장애물이 없어서 그냥 위, 아래로 움직여서 끝 점의 r좌표랑 맞추고, 오른쪽, 왼쪽으로 움직여서 끝 점의 c좌표랑 맞추면 그게 최단 경로다.

 

근데 bfs로 풀어서 제출해도 정답 처리는 된다. 레벨2 문제라 실행 시간은 빡세지 않은듯? 하다.

---

풀이한 방법

• 그냥 빡구현
• Point 객체(좌표) 동등성 비교를 위해 equals랑 hashCode 메서드를 오버라이드 하는 부분이 필요한데, 나중을 위해서라도 이건 외워두는게 좋을 듯

---

코드 

import java.util.*;

class Solution {
    static int R;
    static int C; 
    static Map<Integer, Point> pointMap = new HashMap<>();
    
    class Point {
        int x, y;
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
        
        @Override
        public boolean equals(Object obj) {
            if (this == obj) return true;
            if (obj == null || getClass() != obj.getClass()) return false;
            Point point = (Point) obj;
            return x == point.x && y == point.y;
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }
    }
    
    public int solution(int[][] points, int[][] routes) {
        int answer = 0;
        setBoardSize(points);
        setPointMap(points);
        
        int longestRouteDist = 0;
        List<List<Point>> shortestRoutes = new ArrayList<>();
        for (int[] r : routes) {
            List<Point> route = findShortestRoute(r);
            shortestRoutes.add(route);     
            longestRouteDist = (longestRouteDist < route.size()) ? route.size() : longestRouteDist;
        }
        
        answer = findStrikeCount(shortestRoutes, longestRouteDist);
        return answer;
    }
    
    public void setBoardSize(int[][] points) {
        int r = 0;
        int c = 0;
        for (int[] point : points) {
            if (point[0] > r) {
                r = point[0];
            }
            if (point[1] > c) {
                c = point[1];
            }
        }
        R = r;
        C = c;
    }
    
    public void setPointMap(int[][] points) {
        for (int i = 0; i < points.length; i++) {
            pointMap.put(i + 1, new Point(points[i][1], points[i][0]));
        }
    }
    
    public int findStrikeCount(List<List<Point>> shortestRoutes, int longestRouteDist) {
        int totalCount = 0;
        
        for (int i = 0; i < longestRouteDist; i++) {
            Map<Point, Integer> countMap = new HashMap<>();
            
            for (List<Point> shortestRoute : shortestRoutes) {
                Point point = (shortestRoute.size() > i) ? shortestRoute.get(i) : null;
                if (point != null) {
                    if (countMap.get(point) == null) {
                        countMap.put(point, 1);
                        continue;
                    }
                    countMap.put(point, countMap.get(point) + 1);
                }
            }
            
            for (Integer count : countMap.values()) {
                if (count > 1) {
                    totalCount += 1;
                }
            }
        }
        return totalCount;
    }
    
    public List<Point> findShortestRoute(int[] routePoints) {
        List<Point> shortestRoute = new ArrayList<>();
        for (int i = 1; i < routePoints.length; i++) {
            Point start = pointMap.get(routePoints[i - 1]);
            Point end = pointMap.get(routePoints[i]);
            int r = start.y;
            int c = start.x;
            
            if (shortestRoute.isEmpty()) {
                shortestRoute.add(new Point(r, c));
            }
            
            while (r != end.y) {
                r += (r > end.y) ? -1 : 1;
                shortestRoute.add(new Point(r, c));
            }
            
            while (c != end.x) {
                c += (c > end.x) ? -1 : 1;
                shortestRoute.add(new Point(r, c));
            }
        }
        return shortestRoute;
    }
    
}