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

 

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 생각보다 구현이 까다로웠던 문제다.

특정 위치에서 로봇들이 서로 충돌하는지 파악하고 그 지점의 수를 더하면 되는 문제다.

 

다양한 방법이 있겠지만, 기본적으로 로봇이 움직이는 규칙이 있기 때문에 row 위치가 다르면 row방향으로 움직이고 그다음에 column방향이 다르면 column방향으로 이동하는 움직임을 한다.

 

그러므로 이를 이용해 특정시간에 로봇들의 위치를 파악하면 어느 위치에서 겹치는지 파악할 수 있다.

 

처음에는 각 r * c * 시간 으로 3차원 vector를 만들어 저장하려고 했다. 하지만, 이렇게 구현할 경우 100*100*10000 이 필요할 수 있겠다는 생각이 들어 생각을 바꿨다.

 

queue를 이용해 로봇이 움직인 위치를 계산해 겹치는 지 파악한다.

이후 로봇이 최종 목적지에 도착하면 queue에서 제거하고 최종 목적지에 도착하지 않았다면 queue에 다시 넣는 식으로 코드를 구현했다.

 

같은 위치에 충돌위험이 있는 로봇이 있는지는 2차원 vector에 count를 1씩 더하며 count가 2가 되는 순간만 충돌위험을 1 추가했다.

count가 2보다 클 경우 이미 2일 때 현재 위치에 충돌위험이 있음을 검사했으므로 무시하면 된다.

 

풀이 방법은 어렵지 않았지만, 정보를 저장할 struct를 만드는게 귀찮은 문제였다.

 

풀고 보니 vector대신 unordered_map을 이용해 iterator로 체크하는 방법도 괜찮지 않을까? 라는 생각이 들었다

 

 

[아이디어 정리]

1. 로봇은 항상 r방향으로 먼저 움직이고 r위치가 같다면 c위치를 바꾼다.
2. r과 c위치가 목적지와 같다면, 다음 목적지를 타겟으로 한다.
3. 최종목적지에 도착하면 queue에서 로봇을 제거한다.
4. 충돌위험이 있는지는 로봇이 이동했을 때, 그 위치에 다른 로봇이 방문한 적이 있는지 count를 세 count가 2일 경우만 충돌위험을 1 올린다.

 

 

Code

 

 

 

#include <string>
#include <vector>
#include <queue>
using namespace std;


struct robot
{
    int route;
    int nIdx;
    int r;
    int c;
    bool finish;
};

void move(vector<vector<int>> &points, robot &rr, vector<vector<int>> &routes)
{
    int nr=points[routes[rr.route][rr.nIdx]-1][0];
    int nc=points[routes[rr.route][rr.nIdx]-1][1];
    if (nr==rr.r&&nc==rr.c)
    {
        rr.nIdx+=1;
        if (rr.nIdx>=routes[rr.route].size()){
            rr.finish=true;
            return;
        }
        nr=points[routes[rr.route][rr.nIdx]-1][0];
        nc=points[routes[rr.route][rr.nIdx]-1][1];
    }
    if (rr.r<nr)
    {
        rr.r+=1;    
    }
    else if (rr.r>nr){
        rr.r-=1;
    }
    else if(rr.c<nc){
        rr.c+=1;
    }
    else if(rr.c>nc) 
    {
        rr.c-=1;
    }
    return;
}

int solution(vector<vector<int>> points, vector<vector<int>> routes) {
    int answer = 0;
    vector<vector<int>> prev(101,vector<int>(101,0));
    robot rr;
    queue<robot> q;
    vector<vector<int>> visited(101,vector<int>(101,0));    
    for (int i=0; i<routes.size(); i++){
        rr.route=i;
        rr.r=points[routes[i][0]-1][0];
        rr.c=points[routes[i][0]-1][1];
        rr.nIdx=1;
        rr.finish=false;
        q.push(rr);
        visited[rr.r][rr.c]+=1;
        if (visited[rr.r][rr.c]==2){
            answer+=1;
        }
    }
    while(!q.empty())
    {
        visited=vector<vector<int>>(101,vector<int>(101,0));
        queue<robot> nq;
        while(!q.empty())
        {
            rr=q.front();
            q.pop();
            move(points, rr, routes);
            if (!rr.finish)
            {
                nq.push(rr);
                visited[rr.r][rr.c]+=1;
                if (visited[rr.r][rr.c]==2){
                    answer+=1;
                }
            }
        }
        q=nq;
    }
    
    return answer;
}

---

 

 

구현문제가 오히려 난이도가 더 어렵게 느껴지는 경우가 많은데 표기 난이도는 낮은 것 같다...

오랜만에 풀었더니 은근 힘드네;;

 

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

프로그래머스