[백준] 15686번 치킨배달
-
각 칸
- 빈칸 : 0
- 집 : 1
- 치킨집 : 2
-
r행, c열
- 1행 1열부터 시작함
-
치킨 거리 : 집과 가장 가까운 치킨집 사이의 거리
- 각각의 집은, 치킨거리를 갖고 있다.
-
도시의 치킨 거리 : 모든 집의 치킨 거리의 합
-
두 칸 사이의 거리 : | r1-r2|+|c1-c2|
도시에서 가장 수익을 많이 낼 수 있는 치킨집의 개수 는 “최대 M개 “ 다 .
- 최대 M개를 제외하고는, 모두 폐업시킬 거다.
- “도시의 치킨 거리가 가장 작게” 하는 방법???
- 도시의 치킨거리의 최솟값?
문제 이해
최대 M개를 고른다?
M개 이하를 고를 수있나? → 아닐 듯.. 왜냐하면, 존재하는 치킨집이 많을 수록, 치킨거리는 작을 수 밖에 ( 어떤 집에서 가장 가깝던 치킨집이 사라질수가 있는것이니, “도시의 치킨거리를 최소로” 하는게 목표니까. 최대한, 어떤 집에서 가장 가까운 거리의 치킨집일 수도 있는 치킨집들을 남겨놔야함 )
조건
- N은 50이하
- 집의 개수 : 2N이하
- 치킨집 개수는 M이상 13이하
문제 풀이
나에겐 너무 어려웠다.
계속해서 시간초과가 떴다. 로직을 보면 다른 사람들과 같은 것 같은데
“조합”을 구현한다는 것에서 계속 실수를 하고 있었다.
실수도 실력인데.. 그 실수로 몇 시간을 잡아 먹고, 다른 사람의 코드와 비교하는 과정에서도 조급해서 세부적인 것을 보지 못했다. 로직만 비교해서 맞을 때면, 분명 무언가 실수가 있다는 사실을 명심하자.
치킨 거리 정의 자체가, 어떤 집에서 1. 가장 가까운 치킨집을 찾아 → 2. 그 치킨집까지의 거리
도시의 치킨 거리는, 모든 집의 치킨 거리의 합이다.
- 따라서, 각 집에서 치킨 거리 계산은 필요함
- 그런데 여기서 고려할 것은, A에서는 치킨거리인 치킨집이 B에서는 가장 먼곳일 수 있다는 것
- 폐업대상을 어떻게 결정할것인가?
각 집을 기준으로 대상을 고르지 말고
- 치킨집을 기준으로 골라보자.
바둑판문제가 생각나는데.. row 상에서 탐색하고 col에서 탐색..
row상에서먼저, 각 치킨집들이, 집들과 갖는 거리를 저장
col상에서 각 치킨집들이 집들과 갖는 거리를 저장
- row + col 을 한 결과를 오름차순으로 정렬 →
- 💥💥💥 이게 아님.. 이거 아니다 잘못된 생각 . 이렇게 하면 정확한 정답을 구할 수가 없다.
조건을 보니 각 개수가 상당히 작다.
어쩌면 브루트 포스로 풀어도 될수도 있겠다는 생각이 들었다.
- 최대 13개의 치킨집중에서 M개를 뽑는 경우의 수 (조합)→ 최대 몇 천
- 각 경우의 수에서 도시의 최대거리 계산 → 치킨집의 수는 최대 13이니, 하나의 경우당 13x100
틀림 → 시간 초과
- 현재 나는, chicken에 대해서는, List에 넣어두었었다.
- 하지만 home은 좌표를 돌고 있다보니, 매 번 강제로 2500개를 조회하고 있었다.
- home 또한 List로 저장 - random 접근이 가능해야하므로 JAVA의 ArrayList 를 사용 .
- 두 번째 : 각 집에서 picked에 대해 최소거리를 구할 때 pciked라는 배열을 따로 두지 않아도 된다. 그냥 isPicked boolean array만 두고, 기존에 dfs 를 통한 조합 생성을 하면 된다.
- 💥💥백트래킹.. -> 내가 하고 있던 백트랙킹은 조합이 아닌 순열이었다..ㅠㅠ
심각하게 틀렸던 부분
public static void pickChicken(int cnt){
if(cnt == m){
citySum = Math.min(citySum,evalCityDist());
return;
}
int len = chicken.size();
for(int i=0;i<len;i++){
if(isPicked[i]) continue;
isPicked[i] = true;
pickChicken(cnt+1);
isPicked[i] = false;
}
}내가 하고 있던 것은.. 순열이었다.
조합을 하고 있다고 생각하고 있었으니 원인을 찾지 못하고 몇 시간이나 헤메었고
다른 사람들의 코드를 비교하는 과정에서도 로직만 보면서 맞는데?? 이러고 있었다.
- 당연히 순열과 조합의 경우의 수는 기하급수적임.. 그러다보니 시간초과가 나왔다.
- 여기서는 선택한 치킨집 다음 것부터 선택가능하게 해 줘야 한다.
조합이기 위해선 다음과 같이 변경해 줘야 한다 .
public static void pickChicken(int start, int cnt){
.....
for(int i=start;i<len;i++){
isPicked[i] = true;
pickChicken(i+1,cnt+1);
isPicked[i] = false;
}
}import java.io.*;
import java.util.*;
public class Main {
public static int m;
public static int n;
// 도시거리 최소 구하기
public static int citySum = Integer.MAX_VALUE;
public static List<Loc> chicken = new ArrayList<>();
public static List<Loc> home = new ArrayList<>();
// 선택된 치킨집 조합
public static boolean[] isPicked;
static class Loc{
int r;
int c;
public Loc(int r, int c) {
this.r = r;
this.c = c;
}
}
public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
public static StringTokenizer st;
public static void setting() throws IOException {
st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
int temp = 0;
for(int r=0;r<n;r++){
st = new StringTokenizer(br.readLine());
for(int c=0;c<n;c++){
temp = Integer.parseInt(st.nextToken());
if(temp == 2) chicken.add(new Loc(r,c));
else if(temp == 1) home.add(new Loc(r,c));
}
}
isPicked = new boolean[chicken.size()];
}
public static void pickChicken(int start, int cnt){
if(cnt == m){
int sum = 0;
// 일련의 치킨집이 선택되고 나면 (M개)
// 모든 집으로부터의 각각의 치킨거리를 계산한다.
// 각 집의 치킨거리를 모두 합하여 -> citySum을 업데이트한다.
for(int i=0;i<home.size();i++){
int dist = Integer.MAX_VALUE;
for(int ch = 0 ; ch < chicken.size();ch++){
if(!isPicked[ch]) continue;
dist = Math.min(dist,Math.abs(home.get(i).r - chicken.get(ch).r)+Math.abs(home.get(i).c - chicken.get(ch).c ));
}
sum+=dist;
}
citySum = Math.min(sum,citySum);
return;
}
int len = chicken.size();
// 조합 - 이번에 선택한 idx 다음 것 부터 선택해야 한다.
for(int i=start;i<len;i++){
isPicked[i] = true;
pickChicken(i+1,cnt+1);
isPicked[i] = false;
}
}
public static void main(String[] args) throws IOException{
setting();
pickChicken(0,0);
System.out.println(citySum);
}
}