[백준 15686]치킨배달/삼성 sw역량테스트 기출(java)

문제보러가기

15686번: 치킨 배달

굉장히 어려운 문제는 아니었던것 같다.

 

다른분들은 어떻게 풀었는지 모르겠으나 나는 치킨집의 모든 조합을 다해본 후 집과의 거리를 구해서 가장 작은걸 답으로 고르는 방식으로 풀었다.

 

다른 좋은 방법들이 많은거 같으니 다른분들 푼걸 확인해야겠다!

최대한 많이 풀어보려고 하는중!!

package baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;

public class Ex_15686 {
	
	static int minDistance = Integer.MAX_VALUE;
	static ArrayList<Point> house;
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		ArrayList<Point> chicken = new ArrayList<Point>() ;
		house = new ArrayList<Point>() ;
		String[] str = in.readLine().split(" ");
		int n = Integer.parseInt(str[0]);
		int m = Integer.parseInt(str[1]);
		int[][] g = new int[n][n];
		for (int i = 0; i < n; i++) {
			str = in.readLine().split(" ");
			for (int j = 0; j < n; j++) {
				g[i][j] = Integer.parseInt(str[j]);
				if(g[i][j]==1) house.add(new Point(i,j));
				if(g[i][j]==2) chicken.add(new Point(i,j));
			}
		}
		boolean[] visited = new boolean[chicken.size()];
		chickenSet(chicken, visited, 0, chicken.size(), m);
		System.out.println(minDistance);

	}
    //가능한 치킨집 조합을 다 구해봄-중복x
	 static void chickenSet(ArrayList<Point> arr, boolean[] visited, int start, int n, int r) {
	        if (r == 0) {
	            int min = getDistance(arr, visited, n);
	            if(min<minDistance)
	            	minDistance = min;
	            return;
	        }

	        for (int i = start; i < n; i++) {
	            visited[i] = true;
	            chickenSet(arr, visited, i + 1, n, r - 1);
	            visited[i] = false;
	        }
	    }
//가능한 치킨집묶음마다 최소거리를 반환
	 public static int getDistance(ArrayList<Point> arr,boolean[] visited,int n){
		int distance=0;
		 for(int i=0;i<house.size();i++){
			 int min=Integer.MAX_VALUE;
			 for (int j = 0; j < n; j++) {
				 int dis = Math.abs(arr.get(j).x-house.get(i).x)+Math.abs(arr.get(j).y-house.get(i).y);
				 if (visited[j] == true)
					 if(dis<min){
						min = dis; 
					 }
			 }
			 distance+=min;
		 }
		 return distance;
	 }

}
class Point{
	int x;
	int y;
	Point(int x,int y){
		this.x =x;
		this.y =y;
	}

}