[백준] 치킨배달 15686 - JAVA

[백준] 치킨배달 15686 - JAVA 풀이

 

문제설명

 

생각해야할 요소

1. 치킨집 중에서 최대 M 개를 고른다. ( M개보다 적게 고를 수 있다. )

2. 치킨집을 어떻게 고를 것인가? ( 백트래킹, 조합 )

3. 도시의 치킨 거리는 어떻게 구할 것인가?

 

문제풀이방법

1. 치킨집 중에서 최대 M 개를 고른다. ( M개보다 적게 고를 수 있다. )

    - 이 부분은 문제를 풀다가 놓친 부분이다. ( 그냥 M개를 고르면 되는 줄 알았다. )

    - 최대 M개라 하면, M보다 작은 수의 치킨집을 골라도 된다는 말이다.

    - 생각을 했을 때, M보다 작게 뽑게 된다면 치킨과 집간의 거리가 늘어날 것이고 결국 도시의 치킨 거리가 가장 작게 될지 구하지 못할 것이다. 

    - 결국, 무조건 M개를 뽑아야 함을 알 수 있다. 

 

 

2. 치킨집을 어떻게 고를 것인가? ( 백트래킹, 조합 )

    - 시간초과가 나지 않을까 고민했던 부분이다.

    - 다행히도 입력의 범위가 N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 13) 이기 때문에 재귀호출을 하는 조합으로 구현해도 시간초과가 나지 않았다. 

    - 백트래킹으로 M개를 뽑는 방법을 생각했지만, 어떻게 구현하지...?! 고민하면서 구현하지 못했다. ( 추후에 백트래킹으로 리팩토링해서 다시 upload해야겠다. )

 

 

3. 도시의 치킨 거리는 어떻게 구할 것인가?

    - 조합으로 뽑아놓은 치킨집과 입력할 때 저장해두었던 집의 좌표들의 LinkedList를 활용하여 구했다.

    - 미리 좌표를 구해놓지 않는다면 2차원 배열을 다 돌면서 집인 곳을 찾아야 하기 때문에 시간초과가 날 수 있다.

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {

    static int N, M, answer;
    static LinkedList<House> home;
    static LinkedList<House> chickenShop;

    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());
        answer = Integer.MAX_VALUE;

        int[][] city = new int[N][N];
        chickenShop = new LinkedList<>();
        home = new LinkedList<>();

        int chickenCnt = 0;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                city[i][j] = Integer.parseInt(st.nextToken());

                if (city[i][j] == 1) home.add(new House(i, j));
                if (city[i][j] == 2) {
                    chickenShop.add(new House(i, j));
                    chickenCnt++;
                }
            }
        }

        int[] arr = new int[chickenCnt];
        int[] output = new int[M];
        for(int i=0; i<chickenCnt; i++) arr[i] = i;

        combination(arr, output, chickenCnt, M, 0, 0);
        System.out.println(answer);
    }

    public static void combination(int[] arr, int[] output, int n, int r, int index, int depth) {
        if(r == 0) {
            findChickenDistance(output);
        }
        else if( depth == n ) return;
        else {
            output[index] = arr[depth];
            combination(arr, output, n, r-1, index+1, depth+1 ); // 뽑는경우
            combination(arr, output, n, r, index, depth + 1); // 뽑지 않는 경우
        }
    }

    public static void findChickenDistance(int[] output) {
        int result = 0;

        for( House house : home) {
            int minDis = Integer.MAX_VALUE;

            for(int i=0; i<output.length; i++) {
                House chicken = chickenShop.get(output[i]);
                minDis = Math.min(minDis, Math.abs(house.x - chicken.x) + Math.abs(house.y - chicken.y));
            }
            result += minDis;
        }

        answer = Math.min(answer, result);
    }

    static class House {
        int x, y;

        public House(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

 

 

문제링크

www.acmicpc.net/problem/15686

15686번: 치킨 배달