[백준] 1090 체커 - JAVA

출처 - 백준알고리즘

1090번: 체커

---

 

알고리즘

N개의 체커가 주어질 때, 1≤k≤N인 k개의 체커가 같은 칸에 모이도록 이동하는 최소 횟수를 출력.

 

2차원 좌표에서 점들이 주어질 때 모든 점이 모일 수 있는 최선의 선택은 중간값을 찾는 것이다. (주어진 점들의)x좌표의 중간값, y좌표의 중간값을 찾으면 된다. ( 두개의 점이 주어졌을 때, 점간 거리는 |x-x1| + |y-y1| 로, x좌표와 y좌표가 독립적으로 계산되어 더해지기 떄문에 x좌표와 y좌표를 따로 구분지어 중간값을 찾아도 된다.)

 

모든 점들의 최선의 선택을 위해서는 주어진 좌표들 중 중간값을 찾으면 되지만, 문제에서는 임의의 k개가 모이는 최선의 선택을 각각 찾아내야 한다. 중간값(최선의 선택)을 어떤 점으로 하냐에 따라 이동횟수가 달라지기 때문에, 모든 중간값 후보들에 대해 완전탐색을 진행하여 k개를 모을 수 있는 최소 횟수를 구했다.

 

중간값 후보 ? 

위에서 말했듯이 x좌표와 y좌표를 따로 구분지어 각각의 중간값을 찾으면 된다. 주어진 N개의 x좌표와, 주어진 N개의 y좌표를 기준으로 탐색하기 때문에 총 N^2개의 좌표를 탐색할 수 있다.예를들어, 예제 1번과 같은 경우에는 

노란줄이 x좌표, 초록줄이 y좌표이기 때문에 초록색과 노란색이 겹치는 모든 점들 (9개) 이 중간값의 후보가 될 수 있다. 

 

---

구현 알고리즘 

 

1.  주어진 N개의 좌표들을 List에 넣는다.

 

2.  ( 1≤k≤N ) k개의 점들을 모으기 위한 최소횟수를 저장할 배열 min을 생성하여, 최대 정수로 초기화한다. 

 

3.  N개의 좌표들의 x좌표, y좌표를 사용해서 N^2개의 중간값 후보들을 구한다. (이중 for문)

 

4.  중간값 (x,y) 가 주어졌을 때 아래 방법을 통해 최소 횟수를 찾아낸다.

• 우선순위큐 생성 
• (x,y)에서 주어진 N개 좌표까지의 거리를 계산하여 큐에 삽입 
• 우선순위큐에 의하여 거리가 짧은 것부터 저장 
• 큐에서 하나씩 poll() 하며 sum에 더한다. sum과 min값을 비교하여 최소 횟수 갱신 

 

---

 

소스 코드 

import java.util.*;

public class Solution_BaekJoon_1090 {
	private static List<int[]> list; 
	private static int min[]; 
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in); 
		
		int N= sc.nextInt(); //체커의 갯수 
		min = new int[N]; //체커가 같은 칸에 모일떄의 최소 갯수 
		
		Arrays.fill(min, Integer.MAX_VALUE);
		
		list= new ArrayList<>(); 
		while(N-->0) {
			int x=sc.nextInt();
			int y=sc.nextInt();
			
			list.add(new int[] {x,y}); 
		}
		
		/*
		 * 범위 내에 있는 점들에 대해서 각 좌표까지의 거리 
		 * 가장 가까운 k(1~n)개의 합 */
		for(int i=0; i<list.size(); i++) {
			int x = list.get(i)[0];
			for(int j=0; j<list.size(); j++) {
				int y = list.get(j)[1];
				//중간값의 후보에 대해 모두 탐색 
				checkDis(x,y); 
			}
		}
		
		//1개가 모이는건 0 (자연수니까 무조건 1이상) 
		min[0]=0; 
		System.out.print(min[0]);

		for(int i=1; i<min.length; i++) {
			System.out.print(" "+min[i]);
		}
		
		
	}//end of main
	
	/*
	 * (x,y)에서 각 좌표까지의 거리를 구해서, 가장 작은거 n개 더하기 */
	private static void checkDis(int x, int y) {
		PriorityQueue<Integer> que= new PriorityQueue<>();
		
		for(int i=0; i<list.size(); i++) {
			//주어져있었던 4개의 좌표들 
			int lx = list.get(i)[0];
			int ly = list.get(i)[1]; 
			
			que.add(calDis(x,y,lx,ly)); 
		}
		int sum = que.poll();
		int index =1;
		while(!que.isEmpty()) {
			sum+=que.poll(); 
			if(sum < min[index]) min[index] = sum;
			index++;
		}
	
	}//end of checkDis
	
	/*
	 * 현재 탐색 중인 점으로부터 각 좌표까지의 거리 계산 */
	private static int calDis(int x, int y, int lx, int ly) {
		return Math.abs(x-lx) + Math.abs(y-ly); 
	}
	
}//end of class

 

 

[ 중간값의 원리를 사용하는 비슷한 문제 ] 

편의점 14400

백준 14400 - 편의점 2 ( JAVA )

안테나 18310

백준 18310 - 안테나 ( JAVA )