Algorithm - 백준 벡터 매칭

 

 

 

1007번: 벡터 매칭

 

 

문제를 간단히 설명하자면, 임의의 점이 N개 주어진다.

해당 N개의 점을 한 번씩 사용해서 만들 수 있는 벡터들의 합 중 최소값을 찾고, 길이를 구해야 한다.

 

우선 이 문제를 해결하기 위해 벡터의 성질을 알아야 했다.

 

점 (x0, y0)에서 점 (x1, y1)을 향하는 벡터: (x1 - x0, y1 - y0)

점 (x2, y2)에서 점 (x3, y3)을 향하는 벡터: (x3 - x2, y3 - y2)

벡터들의 합: (x1 + x3 - x0 - x2, y1 + y3 - y0 - y2)

 

해결 방법

1. N개의 점 중 N/2개의 좌표는 더하고 나머지 N/2개의 좌표는 빼면 된다.

2. 1번을 진행하며, 최소값을 찾는다.

 

 

 

우선 dfs를 통해 모든 경우의 수를 조회 후, 최소값을 찾아보기로 했다.

 

import java.util.Scanner;

public class Main {
  static int totalX, totalY, target, vx, vy;
  static int[][] arr;
  static double min;

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int T = sc.nextInt();
    for (int i = 0; i < T; i++) {
      int n = sc.nextInt();
      target = n / 2; // 벡터 매칭에 사용될 값. 점의 절반 개수
      arr = new int[n][2];
      totalX = 0;
      totalY = 0;
      min = Double.POSITIVE_INFINITY;
      // 좌표 입력 받기
      for (int j = 0; j < n; j++) {
        int x = sc.nextInt();
        int y = sc.nextInt();
        arr[j] = new int[]{x + x, y + y}; // 원래 좌표의 2배로 저장
        totalX += x; // x 좌표의 총합
        totalY += y; // y 좌표의 총합
      }

      // 시작 인덱스부터 target 이상인 경우에만 탐색 진행
      for (int j = 0; arr.length - j >= target; j++) {
        vx = totalX; // 벡터 x의 합 초기화
        vy = totalY; // 벡터 y의 합 초기화
        vectorCheck(j, 1); // 최소 벡터 합 계산
      }

      // 최소 벡터 합의 제곱근 출력
      System.out.println(Math.sqrt(min));
    }
  }

  // 최소 벡터 합 계산
  private static void vectorCheck(int idx, int depth) {
    vx -= arr[idx][0]; // x 좌표의 총합에서 해당 좌표의 2배만큼 뺌
    vy -= arr[idx][1]; // y 좌표의 총합에서 해당 좌표의 2배만큼 뺌

    if (depth >= target) { // target에 도달한 경우, 이전의 값과 비교하여 최소값 대입
      min = Math.min((long) vx * vx + (long) vy * vy, min);
    }
    else {  // 도달하지 못했다면, 다음 좌표 탐색
      depth++;
      for (int i = idx + 1; arr.length - i >= target - depth + 1; i++) {
        vectorCheck(i, depth);
      }
    }
    // 탐색 후 좌표 복원
    vx += arr[idx][0];
    vy += arr[idx][1];
  }
}

 

 

벡터와 관련된 첫 문제라 많이 어려울거라 생각했지만, 벡터보다는 dfs를 구현하는데에 어려움을 겪었다.

dfs 문제를 좀 더 풀어봐야겠다.