[lv2/pccp 기출 3번] 충돌위험 찾기 - JAVA

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

 

이게 왜 2레벨인지 진짜 모름

 

어려웠던 요인

1. 거쳐가야 할 포인트 수가 가변적이다.

2. 로봇의 도착 시점은 제각각이다. (도착 표시 따로하고, 도착한건 이동 로직 미포함 해야 함)

3. 도착과 맵 밖으로 나감이 따로 존재하고, 시작과 최초 도착시에도 충돌 체크를 해야 한다.

 

풀이

 

1. 로봇이 거쳐가야 할 포인트를 실제 좌표로 바꿔놓는다. = move[]

 

2. while 루프를 돌며,

 

2-1. 충돌 체크

충돌 체크는 로봇의 시작지점(0초인 경우)에서도 이뤄져야 하기 때문에, 이동 동작보다 먼저 한다.

 

2차원 배열로 하면, 매 순간 100*100 크기를 선언해야 해서

map에 key = r + " " + c로 비교했다.

더 좋은 방법이 있을 것 같은데, 일단 로봇 최대 100개라 나쁘진 않은 방법 같다.

 

2-2. 종료조건 판별

모든 로봇이 거쳐간 포인트 수가 전체 포인트 수와 같으면 종료한다.

여기서 판별해야, 처음부터 다 도착해있는 경우(= 모든 로봇의 포인트가 1개)나, 전부 도착한 이후에도 한 번은 비교해야 함을 만족할 수 있다.

 

2-3. 최단거리 이동

r이동이 c이동보다 우선 되어야한다.

벽같은 진로방해 요소가 없으므로 단순히 좌표 차이에 따라 r-- or r++ 해준다.

목표지점에 도달했다면 거쳐간 포인트 수를 올리고 다음 포인트의 인덱스를 가리킨다.

 

 

import java.util.*;

class Solution {

  static class Pos {

    int r, c;

    Pos(int r, int c) {
      this.r = r;
      this.c = c;
    }
  }
  public int solution(int[][] points, int[][] routes) {
    int answer = 0;
    int P = points.length;
    int R = routes.length;
    int RL = routes[0].length;
    int RT = R * RL;
    int rCnt = R;

	// 로봇 별 이동 경로
    Pos[][] move = new Pos[R][RL];
    // 로봇 별 현재 위치
    Pos[] now = new Pos[R];
    // 로봇 별 거쳐간 포인트 목록
    int[] idx = new int[R];
    // 물류 센터를 벗어났는지 여부 (도착과 구분해야 함)
    boolean[] out = new boolean[R];

    for (int i=0; i<R; i++) {
      int[] route = routes[i];

      for(int j=0; j<RL; j++) {
        int p = route[j] - 1; // 0-indexed : 1번 포인터는 0번 idx에 위치
        move[i][j] = new Pos(points[p][0], points[p][1]);

        if(j == 0) {
          now[i] = new Pos(points[p][0], points[p][1]);
        }
      }
    }

    while(true) {

      Map<String, Integer> check = new HashMap<>();

      for(int i=0; i<R; i++) {

        if(out[i]) continue;

        int r = now[i].r;
        int c = now[i].c;

        String key = new String(r +" " + c);
        check.merge(key, 1, (ov, nv) -> ov + 1);

        // 나간 상태는 아니나 목적지에 도달한 경우, 한 번 충돌체크하고 나감 처리
        if(!out[i] && (idx[i] == RL - 1)) {
          out[i] = true;
        }
      }
		
      // 충돌 => 로봇이 2개 이상 위치하는 경우
      for(int v : check.values()) {
        if(v > 1) answer++;
      }

      if(rCnt == RT) break;

      // 로봇 이동
      for(int i=0; i<R; i++) {

        // 마지막 포인트에 있는 상태
        if(idx[i] == RL - 1) continue;

        int r = now[i].r;
        int c = now[i].c;
		
        // 다음 포인트 좌표
        int gr = move[i][idx[i] + 1].r;
        int gc = move[i][idx[i] + 1].c;

        if(r > gr) {
          r--;
        }
        else if(r < gr) {
          r++;
        }
        // r == gr
        else if(c > gc) {
          c--;
        }
        else {
          c++;
        }

        if(r == gr && c == gc) {
          idx[i]++;
          rCnt++;
        }

        now[i].r = r;
        now[i].c = c;
      }
    }

    return answer;
  }

}