[프로그래머스 Level 2] 충돌위험 찾기 (C++)

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

프로그래머스

 

 

생각 흐름

1. 최단 거리를 구해야 하므로 dfs나 bfs를 쓰자고 생각.
2. 초마다 경로를 찍어놔야 하므로 dfs를 사용하기로 결정.
3. 시간 초과가 발생할 것을 인지.
4. 그림을 계속 보다가 출발지에서 도착지까지 각 좌표별로 가감 연산을 해도 충분하다는 것을 발견.
5.  시간 초 별로 각 좌표에서 충돌이 일어났는지 확인 로직 구성
   1. 3차원 배열을 만드려고 했는데 20000*100*100이어서 포기.
   2. 100*100 2차원을 배열을 만들어 경로 좌표에 대해 안 지나면 0, 한 번 지났으면 1, 또 지났으면 2의 값으로 하여 충돌이 발생했는지 판단하기로 결정.
   3. 이 때 반복문의 경우 0~20000(시간초 반복문) -> 0~100(각 경로를 담은 벡터 반복문)으로 구성. 즉, 0초일 때 각 벡터의 좌표를 배열에 저장하는 방식.

 

 

#include <vector>
#include <memory.h>

using namespace std;

vector<vector<int>> v[100];
int checked[101][101];

int solution(vector<vector<int>> points, vector<vector<int>> routes) {
    int answer = 0;
    
    for(int i = 0; i<routes.size(); i++){
        int y = points[routes[i][0]-1][0];
        int x = points[routes[i][0]-1][1];
        v[i].push_back({y,x});
        for(int j=1; j<routes[i].size(); j++){
            int p = points[routes[i][j]-1][0];
            int q = points[routes[i][j]-1][1];
            while(p != y || q != x){
                if(y>p){
                    y--;
                }else if(y<p){
                    y++;
                }else {
                    if(x>q){
                        x--;
                    }
                    else{
                        x++;
                    }
                }
                v[i].push_back({y,x});
            }
        }
    }
    
    for(int i = 0; i<=20000; i++){
        for(int j = 0; j<100; j++){
            if(v[j].size()>=i+1) {
                if(checked[v[j][i][0]][v[j][i][1]]==2){
                    continue;
                }else if(checked[v[j][i][0]][v[j][i][1]]==1){
                    answer++;
                    checked[v[j][i][0]][v[j][i][1]]=2;
                    continue;
                }
                checked[v[j][i][0]][v[j][i][1]]=1;
            }
        }
        memset(checked,0, sizeof(checked));
    }
    
    return answer;
}