[15686] 치킨 배달 in Java

https://www.acmicpc.net/problem/15686

15686번: 치킨 배달

---

접근 방식

1. 조합을 이용해서 최대 M개의 치킨집을 뽑는 경우의 수를 구함

2. 각 집에서의 치킨 거리를 구함

3. 2번 과정을 모든 집에 적용해준 후에 합한 값이 최솟값이 되도록 구현

 

---

시행착오

온갖 시간초과 & 런타임 에러의 연속..

 

1시간가량 삽질을 한 뒤에

잘못된 부분을 찾아냈다

 

combi 함수 내에서

start 변수에 넣어줘야 하는 건 i 였는데,

start+1을 해줘서 생긴 문제 ^^..

이런 사소한 문제 때문에 . . . 

-> 조합에 대해 이제 100% 다 이해했다고 생각했는데이 부분에서 다시 깨달았다.아는 척 했구나 ^^..

 

그래서 다시 조합에 대해 뜯어보고 공부를 진행했다.

 

 

 

인터넷에 올라와있는 코드랑 비교해보면서올려봤는데도 에러가 뜨길래 봤더니

저 부분만 쏙 빼고 고쳤던 게 함정..

 

 

 

순수 내코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main {
    static int N, M; // 행 크기, 열 크기
    static int[][] array; // 맵 정보
    static int[] selected;
    static int minVal=Integer.MAX_VALUE; // 최종 출력값
    static ArrayList<Point> myHouse = new ArrayList<>(); // 우리집
    static ArrayList<Point> chHouse = new ArrayList<>(); // 치킨집
    static int chCnt, myCnt;
    
    static class Point {
        int r;
        int c;
     
        Point(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }
    
    public static void findMin() {
        // 4. 도시의 치킨 거리 구하기
        int answer=0; 
        // 4.1 각 집별로 가장 가까운 치킨집 사이의 거리를 구한다.
        for(int i=0; i<myCnt; i++) {
            int hr=myHouse.get(i).r, hc=myHouse.get(i).c; // 집 위치
            int temp=Integer.MAX_VALUE; // 해당 집에서 가장 가까운 치킨집의 거리 
            for (int j = 0; j < M; j++) {
                int chr=chHouse.get(selected[j]).r, chc=chHouse.get(selected[j]).c;
                int val=Math.abs(hr-chr) + Math.abs(hc-chc); // 치킨거리
                if (temp>val) temp=val; // 치킨거리 최솟값 갱신
            }
            answer+=temp; // 도시의 치킨거리 최솟값 갱신
        }
        
         if(minVal>answer) minVal=answer; // 최종값 갱신
         
    }
    
    public static void combi(int cnt, int start) {
        if(cnt==M) {
            findMin(); // 치킨집 M개선택완료
            return;
        }
        for (int i = start; i < chCnt; i++) {
            selected[cnt]=i; // 치킨집 번호 넣기
            combi(cnt+1,i+1); 
            selected[cnt]=0;
        }
    }
    
    
    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());
        array=new int[N][N];
        selected=new int[M];
        chCnt=0; myCnt=0;
        
        // 1. 맵 입력받기
        for (int i = 0; i < N; i++) {
            st=new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                array[i][j]=Integer.parseInt(st.nextToken());
                if (array[i][j]==2) {
                    chCnt++;
                    chHouse.add(new Point(i, j));
                }
                else if(array[i][j]==1) {
                    myCnt++;
                    myHouse.add(new Point(i, j));
                }
            }
        }
        
        // 3. 조합으로 치킨집의 경우의 수를 구한다.
        combi(0,0);
        
        // 5. 출력
        System.out.println(minVal);
    }
    
}

 

 

---

 

내 코드를 믿지 못하고..

다른 사람 코드를 보고 고친 수정본 코드..

 

package d0812;
 
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
class Point {
    int x;
    int y;
 
    Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}
 
public class n15686 {
    static int N, M; // 행 크기, 치킨값 최대 개수
    static int[][] array; // 맵 정보
    static boolean[] selected;
    static int minVal; // 최종 출력값
    static ArrayList<Point> myHouse; // 우리집
    static ArrayList<Point> chHouse; // 치킨집    
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        N=Integer.parseInt(st.nextToken());
        M=Integer.parseInt(st.nextToken());
 
        myHouse= new ArrayList<>();
        chHouse= new ArrayList<>();
        array=new int[N][N]; // 맵
        
        // 1. 맵 입력받기 & 집과 치킨집 좌표를 array에 보관
        for (int i = 0; i < N; i++) {
            st=new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                array[i][j]=Integer.parseInt(st.nextToken());
                if(array[i][j]==1) { // 집
                    myHouse.add(new Point(i, j));
                }
                else if (array[i][j]==2) { // 치킨집
                    chHouse.add(new Point(i, j));
                }
            }
        }
        selected=new boolean[chHouse.size()]; // 고른 치킨집
        minVal=Integer.MAX_VALUE;
        
        // 3. 조합으로 치킨집의 경우의 수를 구한다.
        combi(0,0);
        bw.write(minVal + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
    public static void combi(int cnt, int start) {
        if(cnt==M) {
            int answer=0; 
            // 4.1 각 집별로 가장 가까운 치킨집 사이의 거리를 구한다.
            for(int i=0; i<myHouse.size(); i++) {
                int temp=Integer.MAX_VALUE; // 해당 집에서 가장 가까운 치킨집의 거리 
                for (int j = 0; j < chHouse.size(); j++) {
                    if(selected[j]) {                    
                        int distance = Math.abs(myHouse.get(i).x - chHouse.get(j).x)
                                + Math.abs(myHouse.get(i).y - chHouse.get(j).y);
                         temp=Math.min(temp, distance);  // 치킨거리 최솟값 갱신
                    }
                }
                answer+=temp; // 도시의 치킨거리 최솟값 갱신
            }
            minVal=Math.min(minVal, answer); // 최종값 갱신
            return;
        }
        for (int i = start; i < chHouse.size(); i++) {
            selected[i]=true; // 치킨집 번호 넣기
//            combi(cnt+1,start+1); -> 이렇게 해서 시간초과 계속 발생.. 
            combi(cnt+1,i+1);
            selected[i]=false;
        }
    }
}
 
/*
치킨 거리 : 집과 가장 가까운 치킨집 사이의 거리
도시의 치킨 거리 : 모든 집의 치킨 거리의 합
가장 많은 수익을 낼 수 있는 치킨집의 개수 : M개

1. 조합으로 경우의 수를 구한다. 
2. 도시의 치킨 거리 계산 (최솟값 구하기)

격자 크기 : N
빈 칸(0), 집(1), 치킨집(2) 
1<=r,c<=N



*/