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

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/340211?language=cpp

프로그래머스

 

풀이 방법

시뮬레이션 문제이다. 

적절한 자료구조 선택과, 시뮬레이션 방법을 선택한 후 구현하면 된다.

 

자료구조 선택

 

로봇을 stuct 자료구조를 이용해서 설정했다.

 

이유 

1. 하나의 로봇이 가져야 할 정보가 많다.

2. 여러 로봇을 헷갈리지 않게 제어하기 위해 여러 자료구조를 사용하는 거보다 구조체가 제어하기 쉬울 거 같다.

 

시뮬레이션 방법 선택

 

큐를 사용한 bfs로 시뮬레이션

 

이유

 

1. 먼저 도착한 로봇을 시뮬레이션에서 제외해 주기 위해 큐를 사용했다.

2. 로봇을 하나 씩 시간에 따라 제어해야 하므로 bfs를 사용했다.

 

충돌 탐지 방법 선택

 

visited 배열과 times 배열 두 개를 사용했다.

 

이유

 

1. 현재 위치에 로봇이 있는지 알아내기 위해 visited 배열을 사용해서 저장

2. 모든 로봇을 동시에 제어할 수 없기 때문에, times배열을 두어 같은 시간의 로봇인지 판단해 같은 시간의 로봇이면 충돌 횟수 증가

3. visited가 1일 때만 충돌횟수를 증가해야 한다. 2대 충돌, 3대 충돌 모두 충돌 1번만 판단하므로

 

코드

 

#include <string>
#include <vector>
#include <memory.h>
#include <queue>
#include <math.h>
using namespace std;
int dy[4] = {1, -1, 0, 0}; // y부터 움직이도록 설계
int dx[4] = {0 ,0, 1, -1};
int ans = 0;

int visited[101][101]; //현재 위치해 있는지 판단하는 함수
int times[101][101]; // 시간을 체크하는 함수
struct Robot {
    // 현재 위치
    int y;
    int x;
    // 도착 위치 좌표
    vector<pair<int, int>> end_p;
    int time;
    int goal;
    
    Robot(int y, int x, vector<pair<int, int>> end_p, int time, int goal) :y(y), x(x), end_p(end_p), time(time), goal(goal)
    {}

    pair<int, int> next_loc() {
        
        if (y == end_p[goal].first && x == end_p[goal].second) { // 목표 지점에 도착한 경우
            goal++;
            if (goal == end_p.size()) { // 마지막 목표도 도착하면
                return make_pair(-1, -1); // 종료
            }
            
        } 
        //어느 방향쪽으로 갈지 체크해야한다.
        // 현재 거리를 설정하고
        // 현재 거리보다 짧아 진 쪽으로 이동한다.     
        
        int goal_y = end_p[goal].first, goal_x = end_p[goal].second;
        int now_dis = abs(y - goal_y) + abs(x - goal_x);
        for (int i = 0;i < 4;i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (abs(ny - goal_y) + abs(nx - goal_x) < now_dis) {
                y = ny, x = nx;
                time++;
                return make_pair(ny, nx); // 다음 위치 리턴
            }
        }
        
    }
    
};

void bfs(vector<vector<int>> points, vector<vector<int>> routes) {
    
    queue<Robot> q;
    for (int i = 0;i < routes.size();i++) { // 로봇 큐에 넣기
        int y = points[routes[i][0] -1][0]; // 출발지
        int x = points[routes[i][0] -1][1];
        // 도착지 여러 개 인경우 다 추가해 준다.
        vector<pair<int, int>> end_p;
        for (int k = 1;k < routes[i].size(); k++) {
            int end_y = points[routes[i][k] -1][0]; // 도착지  
            int end_x = points[routes[i][k] -1][1];        
            end_p.push_back(make_pair(end_y, end_x));
        }        
        if (visited[y][x] == 1) { // 시작 점에서 충돌일어 날 수 있는지 체크
            ans++;
        }
        visited[y][x]++;
        times[y][x] = 0;
        q.push(Robot(y, x, end_p, 0, 0));
    }
    while(!q.empty()) {
        Robot r = q.front();
        q.pop();
        pair<int, int> n_loc = r.next_loc();
        if (n_loc.first == -1 && n_loc.second == -1) { // 목표 지점에 도착
            continue;
        }
        // visited, time 설정하기
        if (times[n_loc.first][n_loc.second] < r.time) { // visited 다시 설정해야한다.
            visited[n_loc.first][n_loc.second] = 1;
            times[n_loc.first][n_loc.second] = r.time;
        }
        
        else { //시간이 같은 경우 (큰 경우는 없다)
            if (visited[n_loc.first][n_loc.second] == 1) { // 충돌 감지 ( 중복 충돌은 제거)
                ans++;
            }
            visited[n_loc.first][n_loc.second]++;
        }
        
        q.push(r);
        
    }
    
}
int solution(vector<vector<int>> points, vector<vector<int>> routes) {
    memset(visited, 0, sizeof(visited));
    
    bfs(points, routes);
    return ans;
}