[프로그래머스] Level 2. 당구 연습

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

프로그래머스

 

해결 방법

핵심 1. 당구 거리는 어떻게 계산할 것인가?

당구에서 벽을 맞고 이동하는 경로는 마치 벽을 거울처럼 반사한 후, 직선 경로를 계산하는 방식으로 접근하면 된다. 윗벽(10) 에서 반사되는 것은 위로 같은 거리만큼 이동한 가상의 공을 생각하고, 두 점사이의 거리를 구한다.

예제1에서 두 공의 위치는 각각 (3,7), (7,7) 이다. 윗벽을 부딪힌 후 빨간공을 맞춘다고 했을때, 가상의 점 (13,7)까지의 거리를 구한다.

 

흰공에서 벽 , 벽에서 빨간공까지의 거리를 각각 구해서 더하는 방법도 있지만, 문제에서는 거리의 제곱을 구하라고 했다. 만약 각각 구할경우, 실제 거리를 구한 후 더하고, 다시 제곱하는 번거로운 일을 해야한다. 

 

핵심 2. 걸러야 하는 예외가 있다 - 흰공이 벽에 부딪히지 않고 바로 빨간공으로 가는 경우

문제에도 설명했다시피, 두 공이 일직선에 있으면서, 흰 공의 경로상에 빨간 공이 있을 경우이다. 그러므로 invalid한지 검사한 후에 , 만약 그렇다면 계산을 스킵하는 처리가 필요하다.

 

#include <string>
#include <vector>
#include <cmath>
#include <climits>
using namespace std;

int dist_sqr(int x, int y, int a, int b){
    return pow(a - x,2) + pow(y-b,2);
}

int get_distance_sqr(int m, int n, pair<int,int> white, pair<int,int> red){
    
    int answer = INT_MAX;
    
    //윗벽
    bool invalid = white.first == red.first && white.second <= red.second; //일직선 상이면
    if(!invalid){  
        answer = min(answer, dist_sqr(white.first, white.second, red.first, 2*n -red.second));
    }
    
    
    //아랫벽
    invalid = white.first == red.first && white.second >= red.second;
    if(!invalid){
        answer = min(answer, dist_sqr(white.first, white.second, red.first, red.second*-1));
    }
    
    //왼벽
    invalid = white.second == red.second && white.first >= red.first;
    if(!invalid){
        answer = min(answer, dist_sqr(white.first, white.second, red.first*-1,red.second));
    }
    
    //오른벽
    invalid = white.second == red.second && white.first <= red.first;
    if(!invalid){
        answer = min(answer, dist_sqr(white.first, white.second, 2*m-red.first , red.second));
    }
    
    return answer;
}
vector<int> solution(int m, int n, int startX, int startY, vector<vector<int>> balls) {
    vector<int> answer;
    
    for(int i=0; i<balls.size(); i++){
        int result = get_distance_sqr(m,n,make_pair(startX,startY),make_pair(balls[i][0], balls[i][1]));
        answer.push_back(result);
    }
    return answer;
}