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

• 프로래머스 Lv2 충돌위험 찾기 문제
  • 해당 문제의 난이도 상승 원인
    • 각 로봇들의 시간에 따른 이동위치에 대한 일치성을 검사하는 것
  • 해당 문제를 해결한 방법
    • 시간(초)를 기준으로 순환문을 생성하여 각 시간에 따른 Int 자료형을 사용하는 위치 테이블을 생성해 이동 시 해당 위치에 +1 하고 해당 위치의 값이 2 이상이면 겹쳐짐으로 판단하여 이것의 개수를 카운팅함
  • 처음 방식에서 변경한 방식
    • 처음
      • 각 로봇을 저장할 자료형을 List로 정하고 작업
    • 변경
      • 그러나 위의 방법은 루트 요소의 길이가 2인 경우에만 정답이고 그 이상이면 문제가 발생하였음 그래서 루트의 특성인 순서를 지키기 위하여 Queue를 사용해 루트의 우선순위를 지키면서 각 요소의 도착지에 도달 시, 그 뒤에 다른 요소가 있는지 체크하고 요소가 있다면 그 요소의 정보로 다시 이동하게 끔 코드를 작성
  • 문제의 핵심
    • 각 로봇의 겹쳐짐을 판별할 방법을 찾기
    • 요소 길이가 길어지면 이를 해결할 방법 찾기
    • 로봇이 이동가능한 맵의 최대 영역 크기인 n*n 으로 겹쳐짐 판별 시, 메모리 과부하가 발생하므로 이를 해결할 방법 찾기

import java.util.*;

public class LV2SearchCrashRisk {
    public static void main(String[] args){
        int[][] points = {
                {1, 1},
                {1, 3}
        };
        int[][] routes = {
                {1, 2, 1, 2},
                {2, 1, 2, 1}
        };

        System.out.print(solution(points, routes));
    }

    public static class Node{
        int cx;
        int cy;
        int tx;
        int ty;
        int routeNum;

        Node(int cx, int cy, int tx, int ty, int routeNum){
            this.cx = cx;
            this.cy = cy;
            this.tx = tx;
            this.ty = ty;
            this.routeNum = routeNum;
        }

        public int getCx() {
            return cx;
        }

        public int getCy() {
            return cy;
        }

        public int getTx() {
            return tx;
        }

        public int getTy() {
            return ty;
        }

        public int getRouteNum() {
            return routeNum;
        }

        public void set(int cx, int cy, int tx, int ty, int routeNum){
            this.cx = cx;
            this.cy = cy;
            this.tx = tx;
            this.ty = ty;
            this.routeNum = routeNum;
        }

        public void addLoc(int cx, int cy){
            this.cx += cx;
            this.cy += cy;
        }

        public int compareToX(){
            int result = 0;
            if(this.cx > this.tx) result = -1;
            else if(this.cx < this.tx) result = 1;

            return result;
        }

        public int compareToY(){
            int result = 0;
            if(this.cy > this.ty) result = -1;
            else if(this.cy < this.ty) result = 1;

            return result;
        }
    }

    public static int solution(int[][] points, int[][] routes) {
        int maxX = 0;
        int maxY = 0;
        int minX = Integer.MAX_VALUE;
        int minY = Integer.MAX_VALUE;

        for(int i = 0; i < points.length; i++){
            int[] point = points[i];
            maxX = Math.max(maxX, point[0]);
            maxY = Math.max(maxY, point[1]);
            minX = Math.min(minX, point[0]);
            minY = Math.min(minY, point[1]);
        }

        int routeLen = routes[0].length;
        int result = 0;

        List<Queue<Node>> queueList = new ArrayList<>();
        for(int k = 0; k < routes.length; k++){
            Queue<Node> queue = new LinkedList<>();
            int[] route = routes[k];
            for(int i = 0; i < routeLen - 1; i++){
                int[] curr = points[route[i] - 1];
                int[] next = points[route[i+1] - 1];

                queue.offer(new Node(curr[0], curr[1], next[0], next[1], k));
            }
            queueList.add(queue);
        }

        List<Node> list = new ArrayList<>();
        for(Queue<Node> queue : queueList){
            list.add(queue.poll());
        }

        while(!list.isEmpty()){
            int[][] map = new int[maxX - minX + 1][maxY - minY + 1];
            Iterator<Node> it = list.iterator();

            while(it.hasNext()){
                Node node = it.next();
                map[node.cx - minX][node.cy - minY] += 1;
                int nx = node.compareToX();
                int ny = (nx != 0) ? 0 : node.compareToY();

                if(nx == 0 && ny == 0){
                    if(!queueList.get(node.routeNum).isEmpty()){
                        Node newNode = queueList.get(node.routeNum).poll();
                        node.set(newNode.getCx(), newNode.getCy(), newNode.getTx(), newNode.getTy(), newNode.getRouteNum());
                        nx = node.compareToX();
                        ny = (nx != 0) ? 0 : node.compareToY();
                    }
                    else{
                        it.remove();
                        continue;
                    }
                }

                node.addLoc(nx, ny);
            }

            for(int[] arr : map){
                for(int a : arr){
                    System.out.print(a + " ");
                    if(a > 1) result++;
                }
            }
        }

        return result;
    }
}