오늘 풀어볼 문제는 ⭐충돌 위험 찾기 이다!

1. 문제 설명

1.2 입출력

입력은 다음과 같이 구성된다.

points
[[3, 2], [6, 4], [4, 7], [1, 4]]
[[3, 2], [6, 4], [4, 7], [1, 4]]
[[2, 2], [2, 3], [2, 7], [6, 6], [5, 2]]

routes
[[4, 2], [1, 3], [2, 4]]
[[4, 2], [1, 3], [4, 2], [4, 3]]
[[2, 3, 4, 5], [1, 3, 4, 5]]

result
1
9
0

첫 번째 예시 입력이다. 현재 첫 번째 사진과 같이 points들의 위치가 입력으로 주어진다.

그 다음 routes는 로봇들의 이동 경로인데, routes의 0번째 인덱스는 출발 points, 이후 n번째 인덱스들은 해당 로봇의 도착 경로 points들을 나타낸다.

즉 다음과 같은 routs 배열은
[[2, 3, 4, 5], [1, 3, 4, 5]]

• 1번 로봇은 2번 points에서 시작, 3,4,5 points를 순서대로 거친다.
• 2번 로봇은 1번 points에서 시작, 3,4,5 points를 순서대로 거친다.

라는 뜻이다.

1.2 조건

1. 항상 최단 경로로 이용
2. 최단 경로가 여러 개라면, r 좌표가 변하는 이동을 c 좌표가 변하는 이동보다 먼저 함.
3. 출발, 도착에서도 충돌이 발생함.
4. 격자는 100*100

---

2. 접근법

1. 하나의 로봇씩 운영함. 대신 각 2차원 격자 내부에는 로봇이 지나간 시간과 충돌여부가 HashMap으로 들어감
   HashMap <Integer, Boolean> map = <지나간 시간, 충돌여부 >

2. 모든 로봇은 지나갈때마다, 본인이 현재 도착한 시간이 map에 잇는지 확인하고, 이미 충돌을 계산했는지 여부 확인
   -> 만약 충돌 계산 안했다면, 충돌여부 true 로 바꾸고 answer++
   -> 충돌 계산 했다면, 넘어감
   -> 흔적이 없다면, <본인 시간, false> 넣어주고 넘어감.

3. 최단 거리 찾기?
   -> r을 먼저 움직이라는 규칙도 존재하기에, bfs 사용해서 최단거리를 찾는 방법은 안통함
   -> r을 먼저 움직이면 된다? -> 도착지까지 r 좌표를 먼저 맞추고, 그 다음 x 좌표를 맞추면 됨.

4. 로봇이 갈 수 있는 points는 여러 개 임이 핵심!!
-> 모든 경로 구간에 대해 시작점부터 도착점 직전까지 흔적을 남김
-> 단, 마지막 도착지점(=로봇 경로의 마지막 포인트)인 경우에만 도착 지점 좌표까지 흔적을 남김

---

3. 코드

import java.util.*;


class Solution {

    static Map<Integer, Boolean> map[][] = new Map[102][102];
    static int points[][];
    static int routes[][];
    static int answer=0;
    public int solution(int[][] pointss, int[][] routess) {
        points=pointss;
        routes=routess;
        
        for(int i=1; i<=100; i++) {
            for(int j=1; j<=100; j++){
                map[i][j] = new HashMap<>();
            }
        }
        
        for(int i=0; i<routes.length; i++) {
            int time = 0;
            int sr = points[routes[i][0] - 1][0];
            int sc = points[routes[i][0] - 1][1];
        
            for (int j = 1; j < routes[i].length; j++) {
                int er = points[routes[i][j] - 1][0];
                int ec = points[routes[i][j] - 1][1];
                boolean isEnd = (j==routes[i].length-1) ? true : false;
                time = findRoute(sr, sc, er, ec, time, isEnd);
                sr = er; 
                sc = ec;
            }
        }
        return answer;
    }
    
    static int findRoute(int startR, int startC, int endR, int endC, int time, boolean isEnd) {
        //r좌표 먼저 맞추기
        int rCount = Math.abs(startR-endR);
        int move;
        
        while(rCount-->0) {
            mark(startR, startC, time);
            time++;
            move = startR>endR ? -1 : 1;
            startR+=move;
        }
    
        int cCount = Math.abs(startC-endC);
        
        //c좌표까지 가기
         while(cCount-->0) {
            mark(startR, startC, time);
            time++;
            move = startC>endC ? -1 : 1;
            startC+=move;
        }
        
        //isEnd가 true일때만 도착지 찍기
        if(isEnd){
            mark(endR, endC, time);
        }
        return time;
        
    }
    
    static void mark(int r, int c, int time) {
        if(map[r][c].containsKey(time)) { 
            if(!map[r][c].get(time)) { // 충돌 계산 안했다면, 충돌여부 -1로 바꾸고 answer++
                answer++;
                map[r][c].put(time, true);
            } // 충돌 계산 했다면, 넘어감
        } 
        else{ // 흔적이 없다면, <본인 시간, false> 넣어주고 넘어감.
            map[r][c].put(time, false);
        }
    }
}