[종만북] 격자 위에서 기존에 있던 점까지의 거리의 합을 최소화하는 위치 찾기 - JAVA

문제 출처 : 종만북 2.3 문제해결 전략

코드설명

2차원 격자 위에서 기존에 있던 점까지의 거리의 합을 최소화하는 위치를 찾아보겠습니다.

 

처음에 이 문제를 보았을때는 단순히 범위를 구한뒤 완전탐색으로 최소값을 구하는 방식으로 진행하는 방법이 떠올랐습니다만, 문제를 분석해보면, 훨씬 더 효율적으로 해결해낼 수 있었습니다.

 

책에서 제시하는 문제의 조건입니다.

두점 사이의 거리는 x좌표의 차이와 y좌표의 차이를 더한 값이 될 것 이비다.

예를 들어 (7, 1) 과 (2, 3) 사이의 거리는 |( 7 - 2 )| + |(1 - 3) | = 7 입니다.

 

어떻게 해결할 수 있을까요?

이 문제를 해결하는 방법으로 책에서는 "문제를 단순화하자", "1차원 형태로 문제를 바꾸어 생각하자" 입니다.

 

기본적으로 문제에 접근하는 방법은, 

어떤 후보 x의 왼쪽에 있는 점들이 오른쪽에 있는 점들보다 많다면 x를 좀 더 왼쪽으로 옮기는 것이 이득이고, 오른쪽에 있는 점이 많다면 오른쪽으로 옮기는 것이 이득입니다. ( 한칸 가까워지면, 더 많은 점에 가까워진다는 의미이겠습니다. )

다르게 표현해보면, 어떤 후보 x의 왼쪽에 있는 점들이 오른쪽에 있는 점들보다 더 멀다면, x를 좀 더 왼쪽으로 옮기는 것이 이득이고, 오른쪽에 있는 점들이 더 멀다면, 오른쪽으로 옮기는 것이 이득입니다.

 

이를 어떻게 "1차원 형태" 혹은 "문제를 단순화"할 수 있을까요?

1. 모든 점들을 x축 위로 사영한 문제1

2. 모든 점들을 y축 위로 사영한 문제2

로 분할합니다.

 

그렇게 각 문제들을 분할시킴으로써 문제가 훨씬 간단해집니다.

테스트예제

책에서 나온 것처럼, 문제 예시를 만들어봅니다.

입력 예시 1

7 
1 9
1 1
2 3
3 5
4 6
7 4
7 1

결과값

3.5714285714285716 4.142857142857143

 

코드

배열을 활용하여 푼 코드입니다.

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static int N;
	public static double answerX = 0, answerY = 0;
	public static int maxWeight = 20;
	public static int[][] position;
	public static boolean[][] projectXandY; 
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		
		position = new int[N][2];
		
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
			position[i][0] = Integer.parseInt(st.nextToken()); //x좌표
			position[i][1] = Integer.parseInt(st.nextToken()); //y좌표
			
			answerX += position[i][0];
			answerY += position[i][1];
//			projectXandY[position[i][0]][0] = true;
//			projectXandY[0][position[i][1]] = true;
		}
		answerX /= N;
		answerY /= N;
		System.out.println(answerX+" "+answerY);
		
	}
	
}

 

객체로 풀어본 코드입니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
	public static int C, N, M;
	public static int answer = 0;
	public static Node[] node; 
	public static int maxWeight = 20;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		node = new Node[N];
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
			double r= Double.parseDouble(st.nextToken());
			double c= Double.parseDouble(st.nextToken());
			node[i] = new Node(r, c);
		}
		
		Node answer = projectAndCalculateAverage();
		System.out.println(answer.r+" "+answer.c);
		
	}
	public static Node projectAndCalculateAverage() {
		Node answer = new Node(0, 0);
		
		for(int i=0;i<N;i++) {
			answer.r += node[i].r;
			answer.c += node[i].c;
		}
		answer.r /= N;
		answer.c /= N;
		return answer; 
	}

}


class Node{
	double r;
	double c;
	public Node(double r, double c) {
		this.r = r;
		this.c = c;
	}
}