[BOJ] 백준 28215 대피소

대피소 갯수가 1~3개로 적기 때문에 가능한 경우: N^4으로 brute-force 완탐 가능

 

[문제]

https://www.acmicpc.net/problem/28215

 

 

[소스 코드]

부분 성공: List를 사용해 선택된 경우, k가 클 경우 사용

import java.io.*;
import java.util.*;

public class Main {
	static int n,k,result = Integer.MAX_VALUE;
	static boolean[] visit;
	static List<int[]> list;
	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());
		k = Integer.parseInt(st.nextToken());
		list = new ArrayList<>();
		visit = new boolean[n];
		for(int i=0;i<n;i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			list.add(new int[] {y,x});
		}
		select(0,0);
		System.out.println(result);
	}
	private static void select(int idx,int cnt) {
		if(cnt==k) {
			count();
			return;
		}
		for(int i=idx;i<n;i++) {
			visit[i] = true;
			select(i+1,cnt+1);
			visit[i] = false;
		}
	}
	private static void count() {
		int max = Integer.MIN_VALUE;
		for(int i=0;i<n;i++) { 
			if(!visit[i]) {
				int[] home = list.get(i);
				int dis = Integer.MAX_VALUE;
				for(int j=0;j<n;j++) {
					if(visit[j]) {
						int[] shelter = list.get(j);
						int diff = Math.abs(home[0]-shelter[0]) + Math.abs(home[1]-shelter[1]);
						dis = Math.min(diff, dis);
					}
				}
				max = Math.max(max,dis);
			}
		}
		result = Math.min(result, max);
	}
}

 

k가 1~3으로 정해진 갯수가 작기 때문에 배열을 사용하는 게 훨씬 효율적

import java.io.*;
import java.util.*;

public class Main {
	static int n,k,result = Integer.MAX_VALUE;
	static int[][] arr;
	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());
		k = Integer.parseInt(st.nextToken());
		arr = new int[n][2];
		for(int i=0;i<n;i++) {
			st = new StringTokenizer(br.readLine());
			arr[i][0] = Integer.parseInt(st.nextToken());
			arr[i][1] = Integer.parseInt(st.nextToken());
		} 
		if(k==1) {
			for(int i=0;i<n;i++) {
				count(i,i,i);
			}
		}
		else if(k==2) {
			for(int i=0;i<n;i++) {
				for(int j=i+1;j<n;j++) {
					count(i,i,j);
				}
			}
		}
		else {
			for(int i=0;i<n;i++) {
				for(int j=i+1;j<n;j++) {
					for(int k=j+1;k<n;k++) {
						count(i,j,k);
					}
				}
			}
		}
		System.out.println(result);
	}
	private static void count(int a,int b,int c) {
		int maxDis = 0;
		for(int i=0;i<n;i++) {
			int res1 = Math.abs(arr[a][0]-arr[i][0]) + Math.abs(arr[a][1]-arr[i][1]);
			int res2 = Math.abs(arr[b][0]-arr[i][0]) + Math.abs(arr[b][1]-arr[i][1]);
			int res3 = Math.abs(arr[c][0]-arr[i][0]) + Math.abs(arr[c][1]-arr[i][1]);
			maxDis = Math.max(Math.min(res1, Math.min(res2, res3)),maxDis);
		}
		result = Math.min(result, maxDis);
	}
}