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

 

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

프로그래머스

 

이 문제는 여러 로봇이 정해진 경로를 따라 이동할 때, 로봇들이 동일한 위치에 도달할 때 발생하는 충돌 상황을 계산하는 문제입니다. 로봇들이 동일한 시각에 동일한 좌표에 도달한다면 충돌 가능성이 있다고 판단합니다. 이를 통해 몇 번의 충돌 위험 상황이 발생하는지 계산해야 합니다.

주요 규칙

1. 로봇은 2차원 좌표 평면에서 최단 경로로 이동합니다. 최단 경로가 여러 개일 경우 r 좌표가 우선적으로 변경됩니다.
2. 같은 시간에 같은 좌표에 2대 이상의 로봇이 모인다면 충돌 위험이 발생합니다.

문제 해결 전략

1. 그래프 초기화: 주어진 points 배열을 사용해 각 포인트의 좌표 정보를 저장합니다. 포인트는 n개의 좌표로 주어지고, 각 포인트마다 고유 번호를 가집니다.
2. 로봇의 이동 경로 계산: 각 로봇의 경로를 따라가며, 로봇이 지나가는 시간별 좌표를 기록합니다. 이 때, 각 시간마다 해당 좌표에 몇 대의 로봇이 모였는지 기록합니다.
3. 충돌 체크: 각 좌표에 동시에 두 대 이상의 로봇이 도착하면 충돌 위험을 계산합니다.
4. 경로 탐색: 각 로봇이 경로를 따라 이동할 때 최단 경로로 이동하도록 시뮬레이션하며 충돌 상황을 체크합니다.
5. 이 문제의 핵심은 각 로봇의 시간별 좌표를 어떻게 저장할 것인가 입니다.

vector<map<pair<int,int>,int>> path;

 

• path[i] : i 시간 로봇들의 위치
• path[i][좌표] : i 시간에 좌표에 있는 로봇의 수
  • 이 값이 2로 변하는 시점에 ans 를 증가시키면 됩니다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

unordered_map<int, pair<int, int>> graph; // 각 포인트의 좌표를 저장하는 맵
vector<map<pair<int,int>,int>> path; // 시간별 좌표에 로봇이 몇 대 모였는지 기록
int ans = 0; // 충돌 상황 횟수

// 각 로봇의 경로를 따라가며 충돌 상황을 기록하는 함수
void createPath(vector<int>& route){
    pair<int, int> last;
    int time = 0;
    for(int i = 0; i < route.size() - 1; i++){
        pair<int, int> begin = graph[route[i]]; // 현재 포인트의 좌표
        pair<int, int> end = graph[route[i+1]]; // 다음 포인트의 좌표
        last = end;

        // 최단 경로를 따라 이동
        while(begin != end){
            path[time][begin]++;
            if(path[time][begin] == 2) ans++; // 2대 이상의 로봇이 모인 경우
            int xDiff = begin.first - end.first;
            int yDiff = begin.second - end.second;

            // r 좌표가 먼저 변하는 규칙
            if (xDiff != 0) {
                if (xDiff < 0) begin.first++;
                else begin.first--;
            } else if (yDiff != 0) {
                if (yDiff < 0) begin.second++;
                else begin.second--;
            }
            time++;
        }
    }

    path[time][last]++;
    if(path[time][last] == 2) ans++;
}

int solution(vector<vector<int>> points, vector<vector<int>> routes) {
    for(int i = 1; i <= points.size(); i++){
        graph[i] = {points[i - 1][0], points[i - 1][1]};
    }
    path.resize(20001); 
    for(auto route : routes){
        createPath(route);
    }

    return ans;
}

 

 

function solution(points, routes) {
  var answer = 0;
  
  let map = new Map();
  let timePos = [];
  for(let i = 0; i<points.length; i++){
    map.set(i + 1, [points[i][0], points[i][1]]);
  }

  function calcDanger(route){

    let time = 0;
    let last = [0,0];

    for(let i = 0; i<route.length - 1; i++){
      let [startX, startY] = map.get(route[i]);
      let [destX, destY] = map.get(route[i + 1]);

      while(startX !== destX || startY !== destY){

        if(!timePos[time]) timePos[time] = {};
        if(!timePos[time][startX]) timePos[time][startX] = {};
        timePos[time][startX][startY] = (timePos[time][startX][startY] || 0 ) + 1;

        if(timePos[time][startX][startY] === 2) answer++;

        if(startX < destX) startX++;
        else if(startX > destX) startX--
        else if(startY < destY) startY++;
        else if(startY > destY) startY--;
        last = [startX, startY];

        time++;
      }
    }

    if(!timePos[time]) timePos[time] = {};
    if(!timePos[time][last[0]]) timePos[time][last[0]] = {};
    timePos[time][last[0]][last[1]] = (timePos[time][last[0]][last[1]] || 0) + 1;
    if(timePos[time][last[0]][last[1]] === 2) answer++;
  }

  for(let r of routes){
    calcDanger([...r]);
  }
 
  return answer;
}

solution(	[[3, 2], [6, 4], [4, 7], [1, 4]], [[4, 2], [1, 3], [4, 2], [4, 3]])

 

import java.util.HashMap;
import java.util.Map;

class Solution {

    Map<String, Integer> timePos; // 시간, x, y = collision  수
    Map<Integer, Map<Integer,Integer>> m;
    int answer= 0;
    public void calcDanger(int[] route){
        int time = 0;
        int[] last = {0,0};


        for(int i = 0; i<route.length - 1; i++){
            Map<Integer, Integer> startPos = m.get(route[i]);
            Map<Integer, Integer> destPos = m.get(route[i + 1]);

            int startX = startPos.keySet().iterator().next();
            int startY = startPos.get(startX);

            int destX = destPos.keySet().iterator().next();
            int destY = destPos.get(destX);

            while(startX != destX || startY != destY){

                String key = time+"-"+startX+"-"+startY;
                timePos.put(key, timePos.getOrDefault(key, 0) + 1);
                if(timePos.get(key) == 2) answer++;

                if(startX < destX) startX++;
                else if(startX > destX) startX--;
                else if(startY < destY) startY++;
                else if(startY > destY) startY--;

                time++;
                last[0] = startX;
                last[1] = startY;
            }
        }

        String key = time+"-"+last[0]+"-"+last[1];
        timePos.put(key, timePos.getOrDefault(key, 0) + 1);
        if(timePos.get(key) == 2) answer++;
    }
    public int solution(int[][] points, int[][] routes) {

        m = new HashMap<>();
        timePos = new HashMap<>();

        for(int i = 0; i<points.length; i++){
            for(int j = 0; j<points[0].length; j++){
                Map<Integer, Integer> tmp = new HashMap<>();
                tmp.put(points[i][0], points[i][1]);
                m.put(i + 1, tmp);
            }
        }

        for(int i = 0; i<routes.length; i++){
            calcDanger(routes[i]);
        }

        return answer;
    }
}

 

회고:

자바도 같이 연습하고자, 풀었던 문제를 또 풀고 있다. 아직 메서드나 자료구조 활용법이 익숙치 않아서 연습을 많이 해야 겠다.

C++ 의 map<int,pair<int,int>> 를 java 에서 사용하고 싶다면 Map<integer, Map<integer,integer>> 를 사용해야 한다.

 

추가: 나중에 알았는데 Point 자료구조를 활용해서 Map<Integer, Point> 로 해도 되었었다... 그랬었다면 레퍼런스를 뒤져가며 int startX = startPos.keySet().iterator().next(); 를 사용하지 않았어도 되었겠지.. 그래도 C++ 에서 iterator 개념은 익숙했기 때문에 금방 적응 한 것 같다.