삼성 SW 역량평가 기출문제 - 피자배달거리

클릭하면 그림이 커집니다.

역시 삼성문제답게 한번더 꼬아 냈다.
마지막에 조합부분을 반대로 생각해서 정리할겸 풀이를 올린다.

public class Main {


    static int answer = Integer.MAX_VALUE;  // 추후 최소값을 비교해서 저장해야하므로 넣은
    static int[] combo; //조합을 저장할 공간
    static int N,M; // 문제에서 언급한 필요값
    static List<Point> home = new ArrayList<>(); // 집의 위치 저장공간
    static List<Point> pizza = new ArrayList<>(); // 피자의 위치 저장공간

    static class Point{ //집과 피자의 주소값을 담기위한 공간
        int x;
        int y;

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

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        //1번
        for(int i=1;i<=N;i++){
            for(int j=1;j<=N;j++){
                int tmp = sc.nextInt();
                if(tmp == 1) home.add(new Point(i,j));
                if(tmp == 2) pizza.add(new Point(i,j));
            }
        }
        combo = new int[M]; //2
        dfs(0, 0);
        System.out.println(answer); //7
    }

    public static void dfs(int compare, int pizPoint) { //6
        if(M == compare){
            //3.5  System.out.println(Arrays.toString(combo));
            int sum = 0;
           for(Point h: home) { //4
               int min = Integer.MAX_VALUE;
               for (int loc : combo) { //3번에서 만들어놓은 조합집합
                   min = Math.min(min, Math.abs(h.x - pizza.get(loc).x) + Math.abs(h.y - pizza.get(loc).y));
               }
               sum += min; //5
           }
            answer = Math.min(answer, sum);

        }
        else {
            for (int i = pizPoint; i < pizza.size(); i++) { //3
                combo[compare] = i;
                dfs(compare+1, i+1);
            }
        }
    }
}

1. 문제에서 home -> pizza 거리를 구하는 공식을 알려준다 그래서 좌표를 받으면서 pizza와 home의 위치를 각각 ArrayList형태로 저장한다. 추후에 get을 사용해야하기 떄문
2. 그 후 combo라는 저장공간을 만들어낸다. combo는 pizza집중에 몇개를 선택해서 고민할지 에대한 변수다. 그림 가운데 참고

3. 그후 DFS 메서드를 통해 재귀를 도는데 else부분을 먼저 주목해보자.
   그림처럼 하나하나 비교해가면서 조합을 만들어낸다. 6C4 즉 6개중에 4개를 뽑는 경우의 수를 나타내는 것이다. 15가지를 출력하면 아래와 같다.

   [0, 1, 2, 3] [0, 1, 2, 4] [0, 1, 2, 5] [0, 1, 3, 4] [0, 1, 3, 5] [0, 1, 4, 5] [0, 2, 3, 4] [0, 2, 3, 5] [0, 2, 4, 5] [0, 3, 4, 5] [1, 2, 3, 4] [1, 2, 3, 5] [1, 2, 4, 5] [1, 3, 4, 5] [2, 3, 4, 5]

   궁금하면 3.5 주석을 지우면 출력할 수 있다. 이처럼 그림은 1번의 상황을 나타낸것이고, 찾는사이즈가 우리가 처음에 설정한 박스크기가 되었을때 해당 재귀를 끝낸다.

4. 만들어놓은 조합을 가지고 집과 하나하나 대조해본다. 그 후 문제에서 알려준 식을 이용해서 비교하여 최소값을 찾는다.
5. 4번 행동이 끝난 후 그 중 가장 작은 값을 저장하고 4번의 행동을 각 기 다른 HOME들과 비교하여 최소값을 찾는다.
6. 이런식으로 3번에서 언급한 15가지 조합을 전부다 비교해서 최소값을 구하고
7. 6이라는 값을 출력하면서 끝이난다.