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

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

프로그래머스

 

 

문제접근법 : bfs문제의 유형입니다. 

문제조건대로 움직이면되고 움직이는 좌표들중에서 겹치는갯수가 2개일때 충돌의 위험표시 라는것만알면

쉽게 풀수있는 문제입니다.

 

소스코드 : 

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

int solution(vector<vector<int>> points, vector<vector<int>> routes) {
    int answer = 0;
    int n = points.size();
    int rn = routes.size();
    int m = routes[0].size();
    vector<int> ridx(rn+1,1);
    queue<tuple<int,int,int>> q;
    for(int i=0;i<routes.size();i++){
        for(int j =0;j<routes[i].size();j++){
            routes[i][j]--;
        }
    }

    for(int i =0;i<rn;i++){
        int p = routes[i][0];
        q.push({points[p][0],points[p][1],i});
    }
    int y1,x1,y2,x2,idx;
    while (!q.empty())
    {
        int qsize = q.size();
        int qsize2 = q.size();
        map<tuple<int, int>,int> s;
        while (qsize--)
        {
            tie(y1, x1, idx) = q.front();
            q.pop();
            int num = routes[idx][ridx[idx]];
            tie(y2,x2)=tie(points[num][0],points[num][1]);
            s[{y1, x1}]++;
            if(s[{y1,x1}]==2)answer++;
            if (y1 == y2 && x1 == x2){
                ridx[idx]++;
                if(ridx[idx]>=m)continue;
                num = routes[idx][ridx[idx]];
                tie(y2,x2)=tie(points[num][0],points[num][1]);    
            }
            if (y1 == y2)
            {
                if (x2 > x1)
                    x1++;
                else
                    x1--;
            }
            else
            {
                if (y2 > y1)
                    y1++;
                else
                    y1--;
            }
            q.push({y1,x1,idx});
        }
    }
    return answer;
}

궁금한점 혹은 모르는점 어떤질문이든 댓글은 언제나 환영입니다.