728x90
문제
15686번: 치킨 배달
크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸
www.acmicpc.net
접근 방식
M개 이상 13개 이하의 치킨집이 있을 때, M개의 치킨집을 골라
가장 적은 치킨 거리를 구해야 한다.
입력만 보면 그래프 문제처럼 보이기도 하지만 그래프를 쓸 일은 없다.
리스트 두 개를 만들어 입력을 받으면서 집과 치킨집의 좌표를 담아준 후에
두 리스트를 반복문을 돌면서 각 집과 치킨집들의 거리를 모두 구해준다.
그 후 백트래킹으로 M개의 치킨집을 고른 후에
선택된 치킨집들과 집들의 치킨 거리를 구한 후
최소 치킨 거리를 비교해 주며 갱신하면 된다.
순서가 다른 중복된 조합까지 반복적으로 계산하면
시간초과가 발생하는 문제이기 때문에
중복된 조합을 피해서 백트래킹을 해줘야 한다.
풀이
class Main {
static int n, m, h, c, answer = Integer.MAX_VALUE;
static ArrayList<Pair> home = new ArrayList<>();
static ArrayList<Pair> chicken = new ArrayList<>();
static int[] selects;
static int[][] distance;
static boolean[] isUsed;
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());
m = Integer.parseInt(st.nextToken());
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++) {
int x = Integer.parseInt(st.nextToken());
if (x == 1) home.add(new Pair(i, j));
if (x == 2) chicken.add(new Pair(i, j));
}
}
c = chicken.size();
h = home.size();
isUsed = new boolean[c];
selects = new int[m];
calculateDistance();
solve(0, 0);
System.out.println(answer);
}
static void calculateDistance() {
distance = new int[h][c];
for (int i = 0; i < h; i++) {
Pair cur = home.get(i);
for (int j = 0; j < c; j++) {
Pair tar = chicken.get(j);
distance[i][j] = Math.abs(cur.x - tar.x) + Math.abs(cur.y - tar.y);
}
}
}
static void solve(int start, int size) {
if (size == m) {
calculateSum();
return;
}
for (int i = start; i < c; i++) {
if (isUsed[i]) continue;
isUsed[i] = true;
selects[size] = i;
solve(i + 1, size + 1);
isUsed[i] = false;
}
}
static void calculateSum() {
int sum = 0;
for (int i = 0; i < h; i++) {
int min = Integer.MAX_VALUE;
for (int j = 0; j < m; j++) {
min = Math.min(min, distance[i][selects[j]]);
}
sum += min;
}
answer = Math.min(answer, sum);
}
static class Pair {
int x, y;
public Pair(int x, int y) {
this.x = x;
this.y = y;
}
}
}
'Java > Algorithms' 카테고리의 다른 글
| [백준] 4358번 : 생태학 (0) | 2024.04.02 |
|---|---|
| [백준] 11559번 : Puyo Puyo (0) | 2024.04.01 |
| [백준] 3055번 : 탈출 (0) | 2024.03.31 |
| [백준] 12100번 : 2048 (Easy) (0) | 2024.03.30 |
| [백준] 14502번 : 연구소 (1) | 2024.03.29 |
