340211. 충돌위험 찾기

문제

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

제한사항

풀이

import java.util.*;

class Solution {
    public int solution(int[][] points, int[][] routes) {
        int answer = 0;
        int[][] pointMap = new int[101][101];
        int n = routes.length;
        
        // 로봇들의 경로 집합
        List<List<int[]>> paths = new ArrayList<>();
        
        // 경로 추적
        for(int[] route : routes) {
            List<int[]> path = findShortestPath(route, points);
            paths.add(path);
        }
        
        int totalTime = paths.stream().mapToInt(List::size).max().orElse(0);

        
        // System.out.println("totalTime: " + totalTime);
        
        int t = 0;
        
        while(t < totalTime) {
            // System.out.println("t: "+ t);

            Map<String, Integer> countMap = new HashMap<>();
            
            for(List<int[]> path : paths) {
            
                if(t<path.size()) {
                    int[] point = path.get(t);
                    String key = Arrays.toString(point);
                    // System.out.println("key: " + key);

                    if(countMap.get(key) != null) {
                        countMap.put(key, countMap.get(key) +1);
                    } else {
                        countMap.put(key, 1);
                    }
                }
            }
            
            for(int value : countMap.values()) {
                if(value>1)
                    answer++;
            }
            
            t++;
            
        }
        
        
        
        // for(int i = 0; i<paths.size();i++) {
        //     System.out.println("경로");
        //     List<int[]> path= paths.get(i);
        //     for(int[] point : path) {
        //         System.out.println("point[]: " + point[0] + "," + point[1]);
        //     }
        // }

        

        
        return answer;
    }
    
    List<int[]> findShortestPath(int[] route, int[][] points) {
        
        List<int[]> shortestRoute = new ArrayList<>();
        for (int i = 1; i < route.length; i++) {
            int[] start = points[route[i - 1]-1];
            int[] end = points[route[i]-1];
            int r = start[0];
            int c = start[1];
            
            if (shortestRoute.isEmpty()) {
                shortestRoute.add(new int[]{r,c});
            }
            
            while (r != end[0]) {
                r += (r > end[0]) ? -1 : 1;
                shortestRoute.add(new int[]{r,c});
            }
            
            while (c != end[1]) {
                c += (c > end[1]) ? -1 : 1;
                shortestRoute.add(new int[]{r,c});
            }
        }
        return shortestRoute;
    }
                        
}

회고

각 루트의 경로를 추적하고 시간 별로 동시에 루트의 움직임을 추적하며 충돌을 하는지 확인해야 하는 문제였다. 처음에 경로를 찾기 위해 bfs를 고려했는데, 방향의 우선순위가 정해져 있고(우선적으로 위아래부터 고려), 장애물이 있지 않기 때문에 큐를 이용해서 탐색할 필요는 없었다. 

루트가 지나는 노드는 2개로 고정이라고 착각했는데 2개가 넘을 수 있었다. 예를 들어 A->B->C로 이동하거나 A->B->C->A로 이동할 수도 있다. 그래서 인접 노드까지의 경로를 탐색하고 기록해놨다가 최종적으로 마지막 노드까지의 경로를 탐색해야 한다. bfs로 탐색해서 인접 노드 간 경로를 이어 붙이려고 했으나 경로를 합치는 과정에서 어려움을 겪었다. 예를 들면 [A, B, C, A] 이 경로의 좌표를 추적할 때, bfs를 이용하면, A->B->B->C->C->A 이런 식으로 합쳐졌다. 물론 인접 노드 간 경로를 추적할 때 앞의 노드를 리스트에서 제거하면 됐지만 번거로운 작업이었다.

이 문제에서 제일 고민 했던 부분은 시간 별 충돌을 파악하는 것이었다. 로봇의 이동 좌표는 기록할 수 있었지만 시간 별로 파악하고 있지 않았기 때문에 이동 좌표가 겹쳐도 이 좌표가 동시간에 겹치는 건지 파악할 수 없었다(동 시간에 겹치면 충돌이라고 봤다).

예시를 분석해보면 1초에 1칸씩 이동하는 꼴이었다. 따라서 경로의 길이가 곧 이동 총시간이다. 루트마다 경로의 길이는 서로 다르기 때문에 총시간은 가장 긴 경로일 것이다.  그래서 각 인덱스(= 시간)마다 좌표를 파악하고 HashMap을 이용하여 동시간에 충돌이 발생하는지 확인을 하였다.

int totalTime = paths.stream().mapToInt(List::size).max().orElse(0);

        
        // System.out.println("totalTime: " + totalTime);
        
        int t = 0;
        
        while(t < totalTime) {
            // System.out.println("t: "+ t);

            Map<String, Integer> countMap = new HashMap<>();
            
            for(List<int[]> path : paths) {
            
                if(t<path.size()) {
                    int[] point = path.get(t);
                    String key = Arrays.toString(point);
                    // System.out.println("key: " + key);

                    if(countMap.get(key) != null) {
                        countMap.put(key, countMap.get(key) +1);
                    } else {
                        countMap.put(key, 1);
                    }
                }
            }
            
            for(int value : countMap.values()) {
                if(value>1)
                    answer++;
            }
            
            t++;
            
        }