프로그래머스 | Level 2 | 당구 연습

Programmers | Level 2 | 당구 연습

Problems

• 📘 Src: Programmers
• 🗂️ Cat: Geometry

󰧭 Description

프로그래머스의 마스코트인 머쓱이는 최근 취미로 당구를 치기 시작했습니다.

머쓱이는 손 대신 날개를 사용해야 해서 당구를 잘 못 칩니다. 하지만 끈기가 강한 머쓱이는 열심히 노력해서 당구를 잘 치려고 당구 학원에 다니고 있습니다.

오늘도 당구 학원에 나온 머쓱이에게 당구 선생님이"원쿠션"(당구에서 공을 쳐서 벽에 맞히는 걸 쿠션이라고 부르고, 벽에 한 번 맞힌 후 공에 맞히면 원쿠션이라고 부릅니다) 연습을 하라면서 당구공의 위치가 담긴 리스트를 건네줬습니다. 리스트에는 머쓱이가 맞춰야 하는 공들의 위치가 담겨있습니다. 머쓱이는 리스트에 담긴 각 위치에 순서대로 공을 놓아가며 "원쿠션" 연습을 하면 됩니다. 이때, 머쓱이는 항상 같은 위치에 공을 놓고 쳐서 리스트에 담긴 위치에 놓인 공을 맞춥니다.

머쓱이와 달리 최근 취미로 알고리즘 문제를 풀기 시작한 당신은, 머쓱이가 친 공이 각각의 목표로한 공에 맞을 때까지 최소 얼마의 거리를 굴러가야 하는지가 궁금해졌습니다.

당구대의 가로 길이 m, 세로 길이 n과 머쓱이가 쳐야 하는 공이 놓인 위치 좌표를 나타내는 두 정수 startX, startY, 그리고 매 회마다 목표로 해야하는 공들의 위치 좌표를 나타내는 정수 쌍들이 들어있는 2차원 정수배열 balls가 주어집니다. "원쿠션" 연습을 위해 머쓱이가 공을 적어도 벽에 한 번은 맞춘 후 목표 공에 맞힌다고 할 때, 각 회마다 머쓱이가 친 공이 굴러간 거리의 최솟값의 제곱을 배열에 담아 return 하도록 solution() 함수를 완성해 주세요.

단, 머쓱이가 친 공이 벽에 부딪힐 때 진행 방향은 항상 입사각과 반사각이 동일하며, 만약 꼭짓점에 부딪힐 경우 진입 방향의 반대방향으로 공이 진행됩니다. 공의 크기는 무시하며, 두 공의 좌표가 정확히 일치하는 경우에만 두 공이 서로 맞았다고 판단합니다. 공이 목표 공에 맞기 전에 멈추는 경우는 없으며, 목표 공에 맞으면 바로 멈춘다고 가정합니다.

• 왼쪽 그림은 친 공이 벽에 맞았을 때의 움직임을 나타낸 그림입니다. 치기 전 공의 위치가 점 A입니다.
• 오른쪽 그림은 친 공이 꼭짓점에 맞았을 때의 움직임을 나타낸 그림입니다. 치기 전 공의 위치가 점 A입니다.

 Constraints

• 3 ≤ m, n ≤ 1,000
• 0 < startX < m
• 0 < startY < n
• 2 ≤ balls의 길이 ≤ 1,000
• balls의 원소는 [a, b] 형태입니다.
  • a, b는 머쓱이가 맞춰야 할 공이 놓인 좌표를 의미합니다.
  • 0 < a < m, 0 < b < n
  • (a, b) = ( startX, startY )인 입력은 들어오지 않습니다.

󰦕 Examples

m	n	startX	startY	balls	result
10	10	3	7	[[7, 7], [2, 7], [7, 3]]	[52, 37, 116]

Solutions

󰘦 Code

import java.util.*;

class Solution {
    public int[] solution(int m, int n, int startX, int startY, int[][] balls) {
        int[] start = new int[]{startX, startY};  // 시작 위치
        int[] dists = new int[balls.length];
        Arrays.fill(dists, Integer.MAX_VALUE);  // 각 공에 대한 최소 거리를 최댓값으로 초기화
        
        for (int i = 0; i < balls.length; i++) {
            for (int[] ref : reflect(start, balls[i], m, n)) {
                dists[i] = Math.min(calc(ref, balls[i]), dists[i]);  // 목표 위치와의 거리 계산 및 최소값 갱신
            }
        }
        
        return dists;
    }
    
    // 반사된 지점 생성
    private List<int[]> reflect(int[] start, int[] target, int m, int n) {
        List<int[]> refs = new ArrayList<>();
        
        // y좌표 기준 반사 - 위와 아래 벽
        if (start[0] != target[0]) {  // 서로 다른 열에 있을 때
            refs.add(new int[]{start[0], 2 * n - start[1]});  // 위쪽 반사
            refs.add(new int[]{start[0], -start[1]});         // 아래쪽 반사
        } else {  // 같은 열에 있을 때
            if (start[1] > target[1]) refs.add(new int[]{start[0], 2 * n - start[1]});  // 목표 공이 더 아래쪽에 있는 경우 위쪽으로 반사
            if (start[1] < target[1]) refs.add(new int[]{start[0], -start[1]});         // 목표 공이 더 위쪽에 있는 경우 아래쪽으로 반사
        }
        
        // x좌표 기준 반사 - 왼쪽과 오른쪽 벽
        if (start[1] != target[1]) {  // 서로 다른 행에 있을 때
            refs.add(new int[]{2 * m - start[0], start[1]});  // 오른쪽 반사
            refs.add(new int[]{-start[0], start[1]});         // 왼쪽 반사
        } else {  // 같은 행에 있을 때
            if (start[0] > target[0]) refs.add(new int[]{2 * m - start[0], start[1]});  // 목표 공이 더 왼쪽에 있는 경우 오른쪽으로 반사
            if (start[0] < target[0]) refs.add(new int[]{-start[0], start[1]});         // 목표 공이 더 오른쪽에 있는 경우 왼쪽으로 반사
        }
        
        return refs;
    }
    
    // 두 좌표 간 거리 제곱 계산
    private int calc(int[] a, int[] b) {
        int dx = a[0] - b[0];
        int dy = a[1] - b[1];
        return dx * dx + dy * dy;  // 거리 제곱 반환
    }
}

 Approaches

이 문제는 두 공 사이의 거리를 최소화하는 원쿠션 경로를 찾는 문제로, 벽에 부딪혀 반사되는 경로를 고려해야 합니다. 주어진 당구대에서 반사를 이용해 가장 짧은 경로를 계산해야 하므로, 반사된 위치를 통해 경로를 최소화하는 방식으로 접근합니다.

1. 문제 분석

이 문제는 당구대의 벽을 한 번 맞은 후 목표 공에 도달하는 가장 짧은 경로를 구하는 문제입니다. 머쓱이가 목표 공에 도달하려면 반드시 벽에 한 번 부딪힌 후 진행해야 하며, 이때 벽에 부딪힐 때마다 입사각과 반사각의 법칙을 따릅니다. 즉, 공의 진행 방향이 벽에 대해 대칭적으로 반사되는 원리를 고려해야 합니다.

당구대는 직사각형 형태의 제한된 공간이며, 머쓱이의 공과 목표 공은 특정 좌표에 위치합니다. 최단 거리를 구하기 위해 목표 공을 기준으로 하는 반사 지점을 활용합니다. 벽을 기준으로 공을 반사시키면, 각 벽에 대해 4개의 대칭적 반사 지점을 만들 수 있습니다. 이 반사 지점들은 실제 경로를 모사한 좌표들이며, 반사 지점에서부터 목표 공까지의 거리를 계산해 유효한 최소 거리를 찾는 방식으로 접근합니다.

반사 지점을 생성하는 방식은, 목표 공이 벽에 반사된 공과 일직선상에 있는 상황을 모사하여 직선 거리를 구하는 효과를 얻습니다. 이렇게 함으로써 복잡한 입사각과 반사각 계산을 단순화하고, 각 경로의 거리를 효율적으로 계산할 수 있습니다. 따라서 반사 지점을 생성하는 방식이 최단 경로를 찾기에 적합하며, 목표 공에 도달하기 위한 최소 거리를 효과적으로 구할 수 있게 됩니다.

문제 해결을 위해 다음과 같은 요소를 고려해야 합니다:

• 반사 지점의 정의: 머쓱이의 위치를 각 벽에 대해 반사하여 네 가지 반사 지점을 정의할 수 있습니다. 예를 들어, 당구대의 위아래 벽에서 반사되면 y 좌표가 뒤집히고, 좌우 벽에서 반사되면 x 좌표가 뒤집히는 형태로 계산됩니다. 이 네 가지 경우의 반사 지점이 모두 잠재적 경로가 됩니다.
• 유효한 경로 조건: 반사 경로 중 실제로 목표 공에 도달할 수 있는 경로만 유효합니다. 만약 머쓱이의 위치와 목표 공의 위치가 동일한 y축 혹은 x축에 위치한 경우, 특정 반사 지점이 목표 공에 도달할 수 없는 경로가 될 수 있습니다. 예를 들어, 머쓱이의 공과 목표 공이 동일한 x축에 위치하는 경우, 반사된 경로가 동일한 축을 따라 진행할 경우 충돌이 발생하지 않을 수 있습니다. 이러한 예외 상황을 고려해, 유효한 경로만 선택해야 합니다.
• 최소 이동 거리의 계산: 반사된 지점들 중 목표 공에 도달할 수 있는 유효한 경로에 대해 거리를 계산하고, 이 중 가장 짧은 거리를 선택합니다. 여기서 거리는 두 점 사이의 유클리드 거리의 제곱으로 계산합니다. 거리의 제곱을 사용하여 제곱근 계산을 생략할 수 있어 연산 효율성을 높일 수 있습니다.

이 문제는 기본적인 기하학적 반사 원리를 활용해 좌표를 확장하고, 효율적으로 최단 경로를 찾아야 하는 문제입니다. 머쓱이의 공이 목표 공에 정확히 도달하는 데 필요한 최소 거리의 제곱을 반환해야 합니다.

2. 접근 방식

문제를 효율적으로 해결하기 위해 각 목표 공에 대해 다음과 같은 단계로 접근합니다.

1. 반사 지점 생성: 머쓱이의 공을 벽에 반사하여 네 가지 반사 지점을 생성합니다. 좌우와 상하 벽을 기준으로 반사된 지점들은 머쓱이의 공을 기준으로 x 또는 y 좌표가 뒤집힌 형태로 나타나며, 이들 지점이 목표 공에 도달할 잠재적인 경로가 됩니다.
2. 유효한 반사 지점 필터링: 생성된 반사 지점들 중 실제로 목표 공에 도달할 수 있는 경로만 선택합니다. 예를 들어, 머쓱이의 공과 목표 공이 동일한 x 또는 y 축에 위치하는 경우, 특정 반사 지점은 불필요하거나 유효하지 않은 경로를 생성할 수 있습니다. 이를 고려해, 반사 경로가 목표 공에 도달할 수 있는지 여부를 판단해 유효한 경로만 필터링합니다.
3. 거리 계산: 유효한 반사 지점에 대해 머쓱이의 공에서 목표 공까지의 거리를 계산합니다. 거리는 두 점 사이의 유클리드 거리의 제곱으로 계산하여 연산 효율성을 높입니다. 계산된 거리 중 가장 짧은 거리를 선택해 현재 목표 공에 도달하기 위한 최소 이동 거리로 기록합니다.
4. 결과 저장: 각 목표 공에 대해 계산된 최소 이동 거리의 제곱을 결과 배열에 저장합니다. 모든 목표 공에 대해 최소 이동 거리의 제곱이 계산되면, 결과 배열을 반환합니다.

이러한 단계를 통해 각 목표 공에 대한 최소 이동 거리를 효율적으로 계산할 수 있으며, 머쓱이의 공이 목표 공에 맞기까지의 최단 경로를 찾는 문제를 해결할 수 있습니다.

3. 작업 초기화 및 거리 배열 설정

머쓱이의 공의 시작 위치를 기준으로 각 목표 공까지의 최소 거리를 계산하기 위한 배열을 초기화합니다. 이 배열은 목표 공의 개수만큼 생성되며, 각 목표 공에 대한 최단 거리를 저장하기 위해 초기에 최대값으로 설정합니다. 이후 각 목표 공마다 최적의 이동 거리를 찾기 위해, 각 벽에서 반사된 위치를 기준으로 최단 경로를 갱신하게 됩니다.

int[] start = new int[]{startX, startY};  // 머쓱이의 공의 시작 위치를 배열로 정의
int[] dists = new int[balls.length];  // 각 목표 공에 대한 최단 거리 배열 초기화
Arrays.fill(dists, Integer.MAX_VALUE);  // 최소 거리 값을 갱신하기 위해 모든 값을 무한대 초기화

4. 반사 지점 생성

각 목표 공에 대해 머쓱이의 공을 벽에 반사하여 생성된 지점들을 탐색합니다. 이 과정에서는 공의 x, y 좌표를 반전시켜 여러 반사 지점을 만들어내며, 이러한 반사 지점들은 잠재적인 이동 경로를 나타냅니다.

for (int i = 0; i < balls.length; i++) {
    List<int[]> refs = reflect(start, balls[i], m, n);  // 각 목표 공에 대한 반사 지점 목록 생성
    ...
}

특히, 머쓱이의 공과 목표 공이 동일한 행이나 열에 위치할 경우에는 특정 벽에서의 반사가 불필요할 수 있습니다. 예를 들어, 두 공의 x 좌표가 같다면 좌우 반사 지점은 제외하고 상하 반사 지점만을 고려하여 탐색을 최적화합니다. 아래 함수에서는 이러한 예외 처리를 통해 효율적인 반사 지점을 생성하며, 불필요한 경로를 배제합니다.

아래 그림과 같이 머쓱이 공과 목표 공이 같은 행이나 열에 있을 때는 불필요한 반사 경로가 제외되도록 예외 처리가 필요합니다.

반사 지점은 다음과 같은 규칙을 따릅니다:

• x 좌표가 다른 경우: 상하 반사 지점을 추가하여 위쪽과 아래쪽 벽에서 반사된 경로를 고려합니다.
• x 좌표가 같은 경우: 목표 공의 y 좌표와 비교하여 상하 반사 지점을 결정합니다. 이때 목표 공이 위쪽에 있을 경우 위쪽 반사 지점을, 아래쪽에 있을 경우 아래쪽 반사 지점을 추가합니다.
• y 좌표가 다른 경우: 좌우 반사 지점을 추가하여 오른쪽과 왼쪽 벽에서 반사된 경로를 포함합니다.
• y 좌표가 같은 경우: 목표 공의 x 좌표와 비교하여 좌우 반사 지점을 선택합니다. 목표 공이 오른쪽에 있으면 오른쪽 반사 지점을, 왼쪽에 있으면 왼쪽 반사 지점을 추가합니다.

이 과정을 통해 생성된 반사 지점 목록은 이후 최단 거리 계산에 활용됩니다.

private List<int[]> reflect(int[] start, int[] target, int m, int n) {
    List<int[]> refs = new ArrayList<>();
    
    // x 좌표가 다를 경우, 상하 반사 지점을 추가
    if (start[0] != target[0]) {
        refs.add(new int[]{start[0], 2 * n - start[1]});  // 위쪽 벽에서 반사된 지점
        refs.add(new int[]{start[0], -start[1]});         // 아래쪽 벽에서 반사된 지점
    } 
    
    // x 좌표가 같을 경우, 목표 공의 y 좌표와 비교하여 상하 반사 지점 결정
    if (start[0] == target[0]) {
        if (start[1] > target[1]) refs.add(new int[]{start[0], 2 * n - start[1]});  // 목표가 위쪽에 있을 경우 위쪽 반사 지점 추가
        if (start[1] < target[1]) refs.add(new int[]{start[0], -start[1]});         // 목표가 아래쪽에 있을 경우 아래쪽 반사 지점 추가
    }
    
    // y 좌표가 다를 경우, 좌우 반사 지점을 추가
    if (start[1] != target[1]) {
        refs.add(new int[]{2 * m - start[0], start[1]});  // 오른쪽 벽에서 반사된 지점
        refs.add(new int[]{-start[0], start[1]});         // 왼쪽 벽에서 반사된 지점
    } 
    
    // y 좌표가 같을 경우, 목표 공의 x 좌표와 비교하여 좌우 반사 지점 결정
    if (start[1] == target[1]) {
        if (start[0] > target[0]) refs.add(new int[]{2 * m - start[0], start[1]});  // 목표가 오른쪽에 있을 경우 오른쪽 반사 지점 추가
        if (start[0] < target[0]) refs.add(new int[]{-start[0], start[1]});         // 목표가 왼쪽에 있을 경우 왼쪽 반사 지점 추가
    }
    
    return refs;  // 모든 가능한 반사 지점을 리스트로 반환
}

5. 반사 지점 거리 계산

생성된 반사 지점들에서 각 목표 공까지의 거리를 계산하여, 그중 가장 짧은 거리를 선택합니다. 각 목표 공에 대해 모든 반사 지점을 탐색하며 최단 거리를 갱신하고, 최종적으로 최소 거리의 제곱 값을 배열에 저장하게 됩니다.

for (int i = 0; i < balls.length; i++) {
    for (int[] ref : reflect(start, balls[i], m, n)) {
        int dist = Math.min(calc(ref, balls[i]), dists[i]);  // 각 반사 지점과 목표 공 간의 거리 계산
        dists[i] = dist;  // 최단 거리로 갱신
    }
}

이때 두 점 사이의 거리는 두 좌표의 x 및 y 좌표 차이를 각각 제곱하여 더한 값으로 계산하며, 이는 피타고라스 정리를 기반으로 한 거리의 제곱입니다. 반사 지점은 상하좌우 벽을 기준으로 생성되며, 각 반사 지점에서 목표 공까지의 거리를 계산해 최단 거리로 기록합니다. 이를 통해 불필요한 이동을 줄이고, 가장 효율적인 경로를 찾습니다.

private int calc(int[] a, int[] b) {
    int dx = a[0] - b[0];  // x 좌표 차이
    int dy = a[1] - b[1];  // y 좌표 차이
    return dx * dx + dy * dy;  // 두 점 간 거리 제곱 반환
}

6. 최단 거리 계산 결과 반환

모든 목표 공에 대해 최단 거리를 계산한 후, 각 목표 공에 도달하기 위한 최소 거리의 제곱 값을 결과 배열에 저장하여 반환합니다. 이 배열에는 각 목표 공에 대해 원쿠션 경로를 통한 이동 거리의 제곱이 저장되며, 이를 통해 머쓱이가 각 공을 맞추기 위한 최적의 경로를 확인할 수 있습니다.

// 각 목표 공에 대해 최단 거리의 제곱을 저장한 배열 반환
return dists;

󰄉 Complexity

• ⏳ TC: O(N)
• 💾 SC: O(N)

각 목표 공에 대해 상하좌우 벽을 기준으로 반사 지점을 생성하고, 최단 거리를 계산하므로 시간 복잡도는 O(N)입니다. 공간 복잡도 또한 각 목표 공의 최소 거리를 저장하는 배열에만 의존하여 O(N)로, 효율적으로 수행됩니다.