[JAVA]백준 치킨배달

1. 좌표값에 대하여 치킨집, 집에 대한 ArrayList를 각각 생성한다.

2. 위의 생성한 ArrayList에 Input받는 동시에 각각의 Dot(x,y)객체를 집어넣는다.

3. 백트래킹을 이용할것이다.

Combination(DFS)

최소값을 택하여 min값에 넣어준다.

min값은 sum에 추가

ex) Calc부분과 min값 구하는 방법 설명

min

0번째치킨집과 1번째 치킨집 중 가까운 거리

 

www.acmicpc.net/problem/15686

 

위의 문제풀이에 대하여 알아보겠다.

1. 좌표값에 대하여 치킨집, 집에 대한 ArrayList를 각각 생성한다.

 

2. 위의 생성한 ArrayList에 Input받는 동시에 각각의 Dot(x,y)객체를 집어넣는다.

 

3. 백트래킹을 이용할것이다.

=>Combination(DFS)을 이용하여, 각각의 집에 대하여 치킨집까지 거리를 계산해서

그중에서 최소값을 택하여 min값에 넣어준다.

해당 min값은 sum에 추가한다.

 

 

ex) Calc부분과 min값 구하는 방법 설명

output	currentM = Calc(person.get(i), chicken.get(output[j] - 1));
0,1	Calc(각 사람, 치킨집(0번째&1번째 선택))
0,2	Calc(각 사람, 치킨집(0번째&2번째 선택))
0,3	Calc(각 사람, 치킨집(0번째&3번째 선택))
1,2	Calc(각 사람, 치킨집(1번째&2번째 선택))
1,3	Calc(각 사람, 치킨집(1번째&3번째 선택))
2,3	Calc(각 사람, 치킨집(2번째&3번째 선택))

첫번째 경우를 살펴보자.

min값에는 특정 집A에 대하여 0번째치킨집과 1번째 치킨집 중 가까운 거리를 대입해주면된다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
class Main {
​​​​static int N;
​​​​static int M;
​​​​static int[][] arr;
​​​​static ArrayList<Dot> chicken;
​​​​static ArrayList<Dot> person;
​​​​static int[] output;
​​​​static boolean[] visited;
​​​​static int result;

​​​​public static void main(String[] args) throws Exception {

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

​​​​​​​​String[] str = br.readLine().split(" ");
​​​​​​​​N = Integer.parseInt(str[0]);
​​​​​​​​M = Integer.parseInt(str[1]);
​​​​​​​​arr = new int[N][N];
​​​​​​​​result = Integer.MAX_VALUE;
​​​​​​​​chicken = new ArrayList<Dot>();
​​​​​​​​person = new ArrayList<Dot>();

​​​​​​​​for (int i = 0; i < N; i++) {
​​​​​​​​​​​​str = br.readLine().split(" ");
​​​​​​​​​​​​for (int j = 0; j < N; j++) {
​​​​​​​​​​​​​​​​arr[i][j] = Integer.parseInt(str[j]);
​​​​​​​​​​​​​​​​if (arr[i][j] == 1) {
​​​​​​​​​​​​​​​​​​​​//1일때는 사람 list에 추가
​​​​​​​​​​​​​​​​​​​​person.add(new Dot(i, j));
​​​​​​​​​​​​​​​​} else if (arr[i][j] == 2) {
​​​​​​​​​​​​​​​​​​​​//2일때는 치킨 list에 추가
​​​​​​​​​​​​​​​​​​​​chicken.add(new Dot(i, j));
​​​​​​​​​​​​​​​​}
​​​​​​​​​​​​}
​​​​​​​​}
​​​​​​​​//-------입력부-------//

​​​​​​​​//치킨 집 선택을 위한 배열 visited, output
​​​​​​​​visited = new boolean[chicken.size()];
​​​​​​​​output = new int[chicken.size()];//combination 고르는것.

​​​​​​​​//치킨 집 선택
​​​​​​​​for (int i = 0; i < chicken.size(); i++) {
​​​​​​​​​​​​visited[i] = true;
​​​​​​​​​​​​ChickenSelection(i, 0);
​​​​​​​​​​​​visited[i] = false;
​​​​​​​​}
​​​​​​​​System.out.println(result);
​​​​}

​​​​//치킨집 선택을 위한 함수
​​​​public static void ChickenSelection(int start, int depth) {
​​​​​​​​output[depth] = start + 1;

​​​​​​​​for (int i = start; i < chicken.size(); i++) {
​​​​​​​​​​​​if (visited[i])
​​​​​​​​​​​​​​​​continue;
​​​​​​​​​​​​visited[i] = true;
​​​​​​​​​​​​ChickenSelection(i, depth + 1);
​​​​​​​​​​​​visited[i] = false;
​​​​​​​​}
​​​​​​​​//치킨집이 선택되었을 경우
​​​​​​​​//(치킨집이 최대 M개 이므로 depth은 M-1 이 되어야한다. 0부터 시작했으니깐)
​​​​​​​​if (depth == M - 1) {
​​​​​​​​​​​​int sum = 0;
​​​​​​​​​​​​int currentM = 0;
​​​​​​​​​​​​//사람이 갈수 있는 치킨집의 경우중 가장 최소값을 선택한다.
​​​​​​​​​​​​//person 한명씩 모든 Chicken 집을 선택하여 최소값을 비교한다.
​​​​​​​​​​​​for (int i = 0; i < person.size(); i++) {//각 사람에 대하여 치킨집까지 거리 구하기
​​​​​​​​​​​​​​​​int min = Integer.MAX_VALUE;
​​​​​​​​​​​​​​​​for (int j = 0; j < M; j++) {
​​​​​​​​​​​​​​​​​​​​currentM = Calc(person.get(i), chicken.get(output[j] - 1));
​​​​​​​​​​​​​​​​​​​​min = Math.min(min, currentM);
​​​​​​​​​​​​​​​​}
​​​​​​​​​​​​​​​​//최소값일 경우 더한다.
​​​​​​​​​​​​​​​​sum = sum + min;
​​​​​​​​​​​​}
​​​​​​​​​​​​//치킨집 경우의 수마다 다른 최소거리중 가장 작은 최소거리를 선택한다.
​​​​​​​​​​​​result = Math.min(result, sum);
​​​​​​​​}
​​​​}

​​​​//위치 거리 계산 함수
​​​​public static int Calc(Dot d1, Dot d2) {
​​​​​​​​return Math.abs(d1.x - d2.x) + Math.abs(d1.y - d2.y);
​​​​}
}

class Dot {
​​​​int x;
​​​​int y;

​​​​Dot(int x, int y) {
​​​​​​​​this.x = x;
​​​​​​​​this.y = y;
​​​​}
}