import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Stack;
import java.util.StringTokenizer;
public class Main {
static int N;
static int M;
static int[][] map;
static ArrayList<Point> chickenMap;
static ArrayList<Point> houseMap;
static Stack<Point> selectedChicken;
static int minDist;
public static void dfs(int start, int cnt) {
if(cnt == M) {
calculate();
return;
}
for(int i = start; i < chickenMap.size(); i++) {
selectedChicken.push(chickenMap.get(i));
dfs(i+1, cnt+1);
selectedChicken.pop();
}
}
public static void calculate() {
int sum = 0;
for(Point house : houseMap) {
int min = Integer.MAX_VALUE;
for (Point chicken : selectedChicken) {
int dist = (Math.abs(house.x - chicken.x)) + (Math.abs(house.y - chicken.y));
min = Math.min(min, dist);
}
sum += min;
//한 집으로부터 최소 치킨 거리가 현재까지 구한 최소 치킨 거리보다 클 경우 유망하지 않기 때문에 가지치기(백트래킹)
if(sum > minDist) {
return;
}
}
minDist = Math.min(sum, minDist);
}
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());
map = new int[N+1][N+1];
chickenMap = new ArrayList<>();
houseMap = new ArrayList<>();
selectedChicken = new Stack<>();
minDist = Integer.MAX_VALUE;
//집과 치킨집의 개수를 구한다.
for(int i = 1; i <= N; i++) {
st = new StringTokenizer(br.readLine());
for(int j = 1; j <= N; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
if(map[i][j] == 2) {
chickenMap.add(new Point(i, j));
}
//집의 좌표값을 미리 저장
if(map[i][j] == 1) {
houseMap.add(new Point(i, j));
}
}
}
dfs(0, 0);
System.out.println(minDist);
}
}
class Point {
int x;
int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
완전탐색 문제로 순열 알고리즘을 이용해서 풀이했다.
1. ArrayList를 이용해서 각 집의 좌표값과 각 치킨집의 좌표값을 구한다.
2. n개의 치킨집 중에서 m개 만큼의 치킨집의 모든 조합의 최소 치킨 거리를 구한다. (dfs + stack 사용)
3. 시간초과를 피하기 위해서 최소 치킨 거리를 구하는 도중에 현재 최소 치킨 거리보다 크다면 백트래킹을 사용한다.
4. 최소 치킨 거리를 출력한다.
'Dev > PS' 카테고리의 다른 글
[백준] 14889 스타트와 링크 java (0) | 2022.02.08 |
---|---|
[백준] 10819 차이를 최대로 java (0) | 2022.02.07 |
[백준] 1186 부분수열의 합 java (0) | 2022.02.02 |
[백준] 1009 분산 처리 java (0) | 2022.01.27 |
[백준] 1920 수 찾기 java (0) | 2022.01.20 |