문제/백준
백준 15686 치킨 배달 [JAVA]
javaju
2021. 10. 23. 23:36
15686번: 치킨 배달
크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸
www.acmicpc.net
풀이 방법
치킨집을 최대 M개 골랐을 때, 도시의 치킨 거리의 최솟값을 구하는 문제였습니다.
도시의 정보가 주어질 때,
1인 경우에는 home 리스트에 2인 경우에는 chicken 리스트에 위치 정보를 넣어주었습니다.
최대 M개의 치킨 집을 선택하기 위해서 조합을 이용했고,
M개를 선택했을 때 check() 메서드에서 집의 위치로부터 치킨집들의 최소 거리를 구해주었습니다.
코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
|
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main_BJ_15686_치킨배달 {
static class info{
int x, y;
public info(int x, int y) {
super();
this.x = x;
this.y = y;
}
}
static int N,M, min=Integer.MAX_VALUE;
static int [][] map;
static ArrayList<info> chicken = new ArrayList<>();
static ArrayList<info> choice = new ArrayList<>();
static ArrayList<info> home = new ArrayList<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new int[N][N];
for(int i=0;i<N;i++) {
st = new StringTokenizer(br.readLine());
for(int j=0;j<N;j++) {
map[i][j] = Integer.parseInt(st.nextToken());
if(map[i][j]==2) chicken.add(new info(i,j));
else if(map[i][j]==1) home.add(new info(i,j));
}
}
comb(0,0);
System.out.println(min);
}
public static void comb(int cnt, int start) {
if(cnt==M) {
check();
return;
}
for(int i=start;i<chicken.size();i++) {
choice.add(new info(chicken.get(i).x, chicken.get(i).y));
comb(cnt+1, i+1);
choice.remove(choice.size()-1);
}
}
public static void check() {
int distance, sum=0;
for(int i=0;i<home.size();i++) {
distance=Integer.MAX_VALUE;
for(int j=0;j<choice.size();j++) {
distance = Math.min(distance, Math.abs(home.get(i).x-choice.get(j).x)+Math.abs(home.get(i).y-choice.get(j).y));
}
sum+=distance;
}
min = Math.min(min, sum);
}
}
|
cs |