[Algorithm] Programmers :: 충돌위험 찾기

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

프로그래머스

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
 
using namespace std;
 
 
struct Robot
{
    int cy, cx;
    int time;
    int destIndex;
    vector<pair<int,int>> dests;
};
 
int visited[105][105][20005] = { 0 };
pair<int, int> pointPositions[105];
 
int solution(vector<vector<int>> points, vector<vector<int>> routes)
{
    int answer = 0;
 
    for (int i = 0; i < points.size(); ++i)
    {
        pointPositions[i+1].first = points[i][0];
        pointPositions[i+1].second = points[i][1];
    }
 
    queue<Robot> q;
 
    for (int i = 0; i < routes.size(); ++i)
    {
        int startY = pointPositions[routes[i][0]].first;
        int startX = pointPositions[routes[i][0]].second;
 
        vector<pair<int, int>> dests;
        for (int j = 1; j < routes[i].size(); ++j)
        {
            int destY = pointPositions[routes[i][j]].first;
            int destX = pointPositions[routes[i][j]].second;
 
            dests.push_back({ destY,destX });
        }
 
        q.push({ startY,startX,0,0,dests });
    }
 
    while (!q.empty())
    {
        Robot robot = q.front();
        q.pop();
 
        if (visited[robot.cy][robot.cx][robot.time] == 0) // 첫방문이면
        {
            ++visited[robot.cy][robot.cx][robot.time];
        }
        else if (visited[robot.cy][robot.cx][robot.time] == 1) // 누군가 방문했었음.
        {
            ++answer;
            ++visited[robot.cy][robot.cx][robot.time];
        }
        
        int curDestY = robot.dests[robot.destIndex].first;
        int curDestX = robot.dests[robot.destIndex].second;
 
        if (robot.cy == curDestY && robot.cx == curDestX) // 목표도착
        {
            ++robot.destIndex; // 다음 목표 설정.
            
            if (robot.destIndex == robot.dests.size()) // 더이상 목표지없으면
            {
                continue;
            }
 
            curDestY = robot.dests[robot.destIndex].first;
            curDestX = robot.dests[robot.destIndex].second;
        }
 
        ++robot.time;
        
        // 최단경로이동.
        if (curDestY - robot.cy > 0) // 목표가 현재보다 아래에 있다면
        {
            ++robot.cy;
            q.push(robot);
        }
        else if (curDestY - robot.cy < 0) // 현재보다 위에 있다면
        {
            --robot.cy;
            q.push(robot);
        }
        else // 목표지와 r값이 같으면
        {
            if (curDestX - robot.cx > 0) // 목표지가 오른쪽에있으면
            {
                ++robot.cx;
                q.push(robot);
            }
            else if (curDestX - robot.cx < 0) // 목표지가 왼쪽에 있으면
            {
                --robot.cx;
                q.push(robot);
            }
        }
    }
 
    return answer;
}
 
 

 

생각보다 아이디어를 금방생각하고 구현했는데, 25%밖에 안뜨길래 뭐가 문제지.. 하고 고민을 많이 했다.

스터디카페였었는데, 시간이 늦어서 집가는길에 문득 visited의 공간이 넉넉치않다는것을 알았다.

그래서 다음날인 오늘와서 0 두개만 추가해주니 바로 통과했다.

 

일단 기본적으로 BFS를 사용했다. 노드에는 현재 위치 cy,cx, 그리고 목적지인덱스, 목적지좌표값들이 들어있는 vector이다.

근데 오늘와서 다시보니 목적지좌표값을 굳이 노드에 저장할필요가 없었다. 좀 귀찮아지긴하는데 로봇마다 경로를 전역으로 들고있다가, while문안에서 목적지에 도착해서 다음도착지 인덱스같은거를 설정하면 어차피 좌표는 뭐 다 고정되어있으니...

 

사실 포인트는 visited[101][101][20005]이다. 이것은 특정좌표에 특정시간대에 누군가 접근을 했느냐를 체크한다.

만약 visited[30][30][3] == 0 이라면,   30,30좌표면서 3초대에 아직 아무도 접근을 안했다는 뜻이다.

1이라면 누군가 그 시간대에 있었다는 거고, 만약 어떤 로봇이 마찬가지로 30,30 좌표면서 3초에 진입했는데 해당값이 1이라면 거기에 누군가가 존재한단 것이니 정답을 카운팅해주면 된다. visited의 해당값은 ++해준다.

 

중요한것은, visited값이 2가 됐다면 이후 같은좌표,같은시간대에 접근하더라도 정답을 카운팅하지 않는다는것이다.

동일좌표, 동일시간대에 로봇들이 충돌했느냐만 중요할 뿐, 몇대가 충돌했는지는 중요하지 않기 때문이다.