[PCCP 기출문제] 3번 [cpp]

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

---

알고리즘 : 그래프 이론

비슷한 유형의 문제 판단 기준

• 시간의 흐름에 따른 상태를 기록하고 이를 분석해야 하는 문제
• 충돌이나 상호작용을 확인해야 하는 경우

핵심

1. routes를 기준으로 로봇의 이동 경로를 모두 기록
2. 이동 경로 기록할때 경유지도 생각하기
3. 전체 경로에서

#include <algorithm>
#include <iostream>
#include <map>
#include <vector>

using namespace std;

// 총 위험 상황의 수를 계산하는 메인 함수입니다.
int solution(vector<vector<int>> points, vector<vector<int>> routes) {
    // 1. routes를 활용해서 모든 로봇의 이동 경로를 기록
    int answer = 0;

    int n = points.size();
    int x = routes.size();

    // 모든 로봇의 경로가 입력될 곳
    vector<vector<pair<int, int>>> robot_positions(x);

    int max_time = 0;

    // 로봇 수 만큼 경로 기록
    for (int i = 0; i < x; ++i) {
        // 로봇의 경로
        vector<pair<int, int>> positions;
        int time = 0;
        // routes는 [출발지, 목적지]로 이루어져 있음
        int start_point = routes[i][0];
        int current_r = points[start_point - 1][0];
        int current_c = points[start_point - 1][1];

        // 출발지 위치 입력
        positions.push_back({current_r, current_c});

        // 목표지점까지 이동 기록
        // 목적지 설정
        // 목적지로 이동할때 여러곳을 경유할 수도 있기때문에 해당 routes의 사이즈만큼 반복
        for (int j = 1; j < routes[i].size(); ++j) {
            std::cout << routes[i].size() << endl;
            int target_point = routes[i][j];
            int target_r = points[target_point - 1][0];
            int target_c = points[target_point - 1][1];

            // r 좌표를 목표 지점까지 이동
            while (current_r != target_r) {
                current_r += (current_r < target_r) ? 1 : -1;
                time += 1;
                positions.push_back({current_r, current_c});
            }

            // c 좌표를 목표 지점까지 이동
            while (current_c != target_c) {
                current_c += (current_c < target_c) ? 1 : -1;
                time += 1;
                positions.push_back({current_r, current_c});
            }
        }

        max_time = max(max_time, time);
        robot_positions[i] = positions;
    }

    // 최대 시간만큼 이동 경로에대한 중첩 확인
    for (int t = 0; t <= max_time; ++t) {
        // 위치별 로봇의 현재 카운트 계산
        map<pair<int, int>, int> position_counts;

        // 시간 순으로 모든 로봇의 위치 확인
        for (int k = 0; k < x; ++k) {
            // 따라서 로봇의 경로가 시간만큼 충족하는지 확인 최대시간이 더 긴데
            // 거리가 짧은 로봇의 경로를 읽으면 오류
            if (t < robot_positions[k].size()) {
                // 시간대별 위치 확인
                pair<int, int> pos = robot_positions[k][t];
                position_counts[pos] += 1;
            }
        }

        for (const auto &entry : position_counts) {
            if (entry.second >= 2) {
                answer += 1;
            }
        }
    }

    return answer;
}