문제 요약
2차원 NxN 도시들이 주어지는데 0은 빈 칸, 1은 집, 2는 치킨집이다.
존재하는 치킨집들 중 주어지는 가능한 치킨집 수 만큼만 남기고
존재하는 각각의 집에서 가장 가까운 치킨집까지의 거리들의 합에 대한 최소값을 구한다.
풀이과정
(1) 치킨집에 대한 조합 구하기
만약 도시에 치킨집이 4개 있는데 2개만 남겨야 한다면 4개의 치킨집들 중 2개를 선택할 수 있는 모든 경우의 수 4C2를 구해야 한다.
4개의 치킨집 각각을 1~4로 번호를 매긴다면
1 2
1 3
1 4
2 3
2 4
3 4와 같은 조합을 구해야 한다.
번호로 표시했지만 실제로는 x,y 좌표를 가져야 할 것이다.
(2) 존재하는 모든 집들에서 조합 하나로부터 얻은 치킨집들을 이용해 가장 가까운 치킨집 거리를 구한다.
모든 집의 좌표를 저장해두었다가 순회하면서 조합으로 얻은 치킨집 좌표 정보들을 가지고 가장 가까운 치킨집과의 거리를 구하면 된다.
총 치킨집 3개 => 2개 필요
- Test Case
[집 o 치 o]
[o o o 치]
[집 o 치 o]예를들어 위와 같은 케이스가 주어지고 치킨집이 두개만 있어야 하는 상황이라면
- 생존 치킨집 조합1: (1,3), (2,4)
[집 o 치 o]
[o o o 치]
[집 o o o]
거리: 2 + 4 = 6
- 생존 치킨집 조합2: (1,3), (3,3)
[집 o 치 o]
[o o o o]
[집 o 치 o]
거리: 2 + 2 = 4
- 생존 치킨집 조합3: (2,4), (3,3)
[집 o o o]
[o o o 치]
[집 o 치 o]
거리: 4 + 2 = 6위와 같이 조합을 모두 만들어보고 가까운 치킨집과의 거리를 구해 더하면 된다.
풀이코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.stream.Collectors;
public class boj15686_치킨배달 {
static int len;
static int chickLimit;
static int[][] array;
static int answer = Integer.MAX_VALUE;
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
int[] infos = Arrays.stream(bufferedReader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
len = infos[0];
chickLimit = infos[1];
array = new int[len][len];
for (int i = 0; i < array.length; i++) {
array[i] = Arrays.stream(bufferedReader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
}
List<ChickenHouse> chickenHouseList = new ArrayList<>();
List<Client> clientList = new ArrayList<>();
// 치킨, 집 좌표 저장
initChickenAndClient(chickenHouseList, clientList);
combinationChicken(clientList, chickenHouseList, 0, 0);
System.out.println(answer);
}
static void findDistance(List<Client> clientList, List<ChickenHouse> chickenHouseList) {
int cnt = 0;
for (Client client : clientList) {
int currentCnt = Integer.MAX_VALUE;
for (ChickenHouse chickenHouse : chickenHouseList) {
currentCnt = Math.min(currentCnt, Math.abs(client.x - chickenHouse.x) + Math.abs(client.y - chickenHouse.y));
}
cnt += currentCnt;
}
answer = Math.min(cnt, answer);
}
static void combinationChicken(List<Client> clientList, List<ChickenHouse> chickenHouseList, int cnt, int idx) {
if (cnt == chickLimit) {
findDistance(clientList,
chickenHouseList.stream().filter(chickenHouse -> chickenHouse.isAvailable).collect(Collectors.toList()));
return;
}
for (int i = idx; i < chickenHouseList.size(); i++) {
chickenHouseList.get(i).isAvailable = true;
combinationChicken(clientList, chickenHouseList, cnt + 1, i + 1);
chickenHouseList.get(i).isAvailable = false;
}
}
static class ChickenHouse extends Point {
boolean isAvailable;
public ChickenHouse(int x, int y) {
super(x, y);
}
}
static class Client extends Point {
public Client(int x, int y) {
super(x, y);
}
}
abstract static class Point {
int x;
int y;
Point(int x, int y) {
this.x = x;
this.y = y;
}
}
static void initChickenAndClient(List<ChickenHouse> chickenHouseList, List<Client> clientList) {
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array[i].length; j++) {
if (array[i][j] == 1) {
clientList.add(new Client(i, j));
continue;
}
if (array[i][j] == 2) {
chickenHouseList.add(new ChickenHouse(i, j));
array[i][j] = 0;
}
}
}
}
}작성하면서 다시 보니까 사실 효율성을 더 개선해야 하는 코드라고 생각한다.
2차원 배열이 전부 필요한 것이 아니고 치킨집과 집의 좌표만 필요한 것이니 해당 부분만 입력받으면서 저장하면 되고
조합을 만드는 재귀 메소드에서도 치킨 객체의 isAvailable 상태를 바꿔가며 순회하고 필터링해서 거리를 구하는 동작에 사용하기 보다는 조건에 부합하는 경우에 대해서 배열로 만들어 거리 계산 메소드로 넘기는 것이 더 적절했을 것 같다.
2차원 배열 길이와 치킨집 갯수 제한이 작기 때문에 충분히 가능했던 방법이라고 생각한다!
