/ BOJ

BOJ_15686_치킨 배달_JAVA

문제 : 치킨 배달

링크 : BOJ_15686_치킨배달

접근 방식

N*N크기의 배열에 들어있는 값을 탐색하며 치킨집의 위치, 집의 위치를 각각 나누어 리스트에 저장한다.

그 후, 치킨집의 개수에서 M개의 치킨집을 고르는 조합을 통해 가능한 치킨집의 경우의 수를 구한다.

구해진 M개의 치킨집과 각각의 집의 최단 거리를 구해서 더한다.

최단거리를 구해서 더한 값을 생성된 조합별로 비교해 그 중에서 가장 작은 값을 구하여 출력하면 된다.

풀이 방법

  1. 좌표정보를 저장할 클래스 Vector을 생성한다. 해당 클래스는 x좌표, y좌표를 멤버 변수로써 가진다.

  2. N*N 크기의 배열을 생성한다, 집의 정보를 저장할 리스트와, 치킨집의 정보를 저장할 리스트를 각각 생성한다.

  3. 배열에 주어진 값을 추가하는데, 해당하는 값이 1(집)이면 집 리스트에, 2(치킨집)이면 치킨집 리스트에 추가한다.

  4. 조합 메서드를 구현하여 적용한다. M개 이상의 치킨집에서 M개만큼 뽑는 조합을 구현한다.

  5. 조합의 기저조건에서, 집 List 길이 * 구해진 치킨집의 개수만큼 이중반복문을 돌린다.

  6. 내부반복문에서 dist의 최소값을 먼저 구하고, 그것을 내부 통합 거리에 더해준다. 그리고, 그 바깥에서 내부통합거리의 최솟값을 구하는 로직을 추가한다.

  7. 모든 조합에 대해 최소 거리를 구하는 작업이 끝난 후, 구해진 최소 통합 거리를 출력한다.

소스 코드


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


class Vector{

	int x;
	int y;
	public Vector(int x, int y) {
		super();
		this.x = x;
		this.y = y;
	}


}

public class BOJ_15686_치킨배달 {


	static int N, M, arr[][];

	static ArrayList<Vector> chList;
	static ArrayList<Vector> hoList;
	static Vector[] chickens;
	static int totalDist = Integer.MAX_VALUE;
	public static void main(String[] args) throws IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(in.readLine()," ");

		N = Integer.parseInt(st.nextToken());


		M = Integer.parseInt(st.nextToken());



		arr = new int[N][N];
		chList = new ArrayList<>();
		hoList = new ArrayList<>();
		chickens = new Vector[M];

		for(int i=0;i<N;i++) {
			st = new StringTokenizer(in.readLine()," ");
			for(int j=0;j<N;j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
				if(arr[i][j] == 2) {
					chList.add(new Vector(i,j));
				}
				if(arr[i][j] == 1) {
					hoList.add(new Vector(i,j));
				}
			}
		}		

		comb(0,0);

		System.out.println(totalDist);
	}

	static void comb(int start, int cnt) {

		if(cnt == M) {
			int inTotalDist = 0;
			for(int i=0,n=hoList.size();i<n;i++) {
				int inMin = Integer.MAX_VALUE;
				for(int j=0;j<chickens.length;j++) {
					int row =  Math.abs(hoList.get(i).x - chickens[j].x);
					int col =  Math.abs(hoList.get(i).y - chickens[j].y);
					int dist = row + col;
					inMin = Math.min(inMin,dist);
				}
				inTotalDist += inMin;
			}
			totalDist = Math.min(totalDist, inTotalDist);
			return;
		}

		for(int i=start, n = chList.size();i<n;i++) {

			chickens[cnt] = new Vector(chList.get(i).x, chList.get(i).y);

			comb(i+1,cnt+1);
		}


	}

}