[프로그래머스] Level 2. 충돌 위험 찾기

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

프로그래머스

 

문제를 이해하는데 오랜시간이 걸렸다. routes가 의미하는게 무엇인지 이해가 잘 안되었었다. 

routes 가 [[4,2],[1,3],[2,4]] 라면 로봇이 총 3개 있는것이고, 1번로봇은 4지점 > 2지점으로, 2번포인트는 1지점>3지점으로, 3번로봇은 2지점 > 4지점으로 이동한다는 의미이다. 

 

주의할 점

• 충돌이 두군데에서 일어나면 2를 더한다는 점이었다. 문제엔 모호하게 나와있는데, 테스트 케이스 2번에서 예시를 볼 수 있다.
• 맨 처음 시작지점에서도 충돌 체크를 해야한다. 이동하면서 체크하는게 아니라, 만약 시작 지점이 동일한 로봇이 있다면 충돌위험 + 1 이다.
• 최종 지점까지 도달하는 시간은 로봇마다 다를 수 있다. 만약 먼저 도착한 로봇이 있을 경우 물류센터를 벗어나고, 더이상 충돌위험 체크에 포함되지 않는다. 그럴 경우 남은 로봇들끼리 충돌체크를 진행한다=

위 3가지때문에 문제 해결이 꽤 오래걸렸다. 

해결 방법

• 모든 로봇을 첫번째 포인트에 위치치키고, 위치 정보를 vector<pair<int,int>> 변수에 담는다. 0번째 pair은 0번째 로봇의 위치값을 의미한다.
• 이상태에서 충돌검사를 한번 한다. 함수 crashCount()는 현재 위치값들의 정보를 받아서, 충돌한 횟수를 의미한다. 두군데에서 충돌이 일어났다면 2를 리턴한다.
• while문을 이용해 충돌검사를 계속한다. 로직은 다음과 같다.
  1. vector<int> route_idx 에는 현재 각 로봇들이 어디를 향해 가고있는지 포인트 인덱스를 담고있다. 0번째 포인트에 이미 위치 시켜놓았으므로, 현재 route_idx의 값은 모두 1이다. 
  2. 모든 로봇들을 돌면서 타겟 route 포인트 번호로 이동한다. 만약 도착했을 경우 route_idx[로봇idx] 를 1 증가시킨다.
  3. 모든 로봇을 다 돌았다면, 충돌검사를 해서 충돌한 칸의 수를 answer에 더한다. 
  4. 도착지점에 도착한 로봇들은 더이상 충돌체크에 검사되면 안되므로, position값을 -1,-1 로 설정한다. (-1,-1) 인 로봇들은 물류센터를 벗어났다는 의미이다. 도착지점에 도착했다는 것은 route_idx[로봇idx] 가 routes[로봇idx] 의 범위를 벗어났다는 것으로 판단한다
• 충돌검사는 다음과 같이 진행한다.
  1. 로봇들의 position를 돌면서 , 충돌한 것이 있다면 그 위치를 crash에 넣어놓고 cnt를 증가시킨다.
  2. 만약 position이 (-1,-1)이라면 물류센터를 벗어났다는 의미이므로 패스한다.
  3. 이미 crash에 들어있다는것은, 같은지점에 3개 이상의 로봇이 있다는 것이므로, cnt를 증가시키지 않고 그냥 넘어간다(이미 카운트 되었으므로)

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

int crashCount(vector<pair<int,int>>& p){
    vector<pair<int,int>> crash;
    int cnt = 0;
    for(int i  =0; i<p.size(); i++){
        if(p[i].first == -1 && p[i].second == -1) continue;
        for(int j = i+1; j<p.size(); j++){
            
            if(p[i].first == p[j].first 
               && p[i].second == p[j].second){
                auto pair = make_pair(p[i].first, p[i].second);
                auto f = find(crash.begin(), crash.end(), pair);    
                if(f == crash.end()){
                    cnt++;
                    crash.push_back(pair);
                }
            }
        }
    }    
    return cnt;
}

int solution(vector<vector<int>> points, vector<vector<int>> routes) {
    int answer = 0;
    vector<int> route_idx(routes.size(),1); 
    vector<pair<int,int>> positions;
    
    //초기 위치로 세팅.
    for(int i =0 ; i<routes.size(); i++){
        
        int point_idx = routes[i][0]-1;
        positions.push_back(make_pair(points[point_idx][0], points[point_idx][1]));
    }
    
	//초기 위치에서 검사 한번 진행   
    answer += crashCount(positions);

    while(true){

        for(int i = 0; i<routes.size(); i++){ //모든 로봇마다 검사
            if(routes[i].size() <= route_idx[i]) continue; //물류센터 벗어난것은 패스
            
            int idx = routes[i][route_idx[i]]-1;
            
            int x= points[idx][0]; 
            int y = points[idx][1]; //방문해야할 다음 포인트
            auto crr = positions[i];
            
            if(crr.first != x) positions[i].first += crr.first < x? 1 : -1;
            else  if(crr.second != y) positions[i].second += crr.second< y ? 1:-1;

			//포인트에 도착하였으므로 다음 포인트로 이동해야함.
            if(positions[i].first == x && positions[i].second == y) route_idx[i]++;
        }
	
    	//모든 로봇이 한칸씩 이동한 시점에서 검사진행
        answer += crashCount(positions);
    
        //마지막 포인트까지 도착했을 경우 (-1,-1) 로 변경, 물류센터를 벗어났음을 표현
        bool flag = false;
        for(int i=0; i<routes.size(); i++){
            if(routes[i].size() <= route_idx[i] ){
                positions[i].first = positions[i].second = -1;    
            }else flag = true;
        }
        
        //모든 로봇이 물류센터를 벗어났을 경우 while문 종료
        if(!flag) break;
    }
   
    
    return answer;
}

 

 

마무리하며

성격이 급해서인지, 테스트 케이스 1번만 보고 문제를 푸는 습관이 있었다. 테스트 1은 정답인데 2,3번이 정답이 아닌 경우가 많이 발생했다. 앞으로는 테스트 케이스를 처음부터 끝까지 꼼꼼하게 잘 읽어봐야겠다. 충돌 체크 함수만 몇번을 수정한건지 모르겠엉..