[인프런/DFS/피자배달거리]

오늘은 조합 문제로서 DFS를 활용해서 알고리즘을 만들어 풀어보았다.

 

해당 문제는 문제의 말이 헷갈리 수도 있고 논란의 소지도 있을 것 같다는 생각이 든다.

 

하지만, 알고리즘에 초점을 두고 배웠다는 생각으로 풀어보았다.

 

 

<<풀이>>

 

import java.util.ArrayList;
import java.util.Scanner;

class Point {
    int x;
    int y;

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



class Main {

    static int answer = Integer.MAX_VALUE;
    static ArrayList<Point> house, pizza;
    static int n, m, len;
    static int[] combi;


    private void DFS(int L, int s) {
        if (L == m) {
            int sum = 0;
            for (Point h : house) {
                int dis = Integer.MAX_VALUE;
                for (int i : combi) {
                    dis = Math.min(dis, Math.abs(h.x - pizza.get(i).x) + Math.abs(h.y - pizza.get(i).y));
                }
                sum += dis;
            }
            answer = Math.min(answer, sum);
        }
        else {
            for (int i = s; i < len; i++) {
                combi[L] = i;
                DFS(L+1, i+1);
            }
        }
    }



    public static void main(String[] args){
        Main T = new Main();
        house = new ArrayList<>();
        pizza = new ArrayList<>();
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();


        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int tmp = in.nextInt();
                if (tmp == 1) house.add(new Point(i, j));
                else if (tmp == 2) pizza.add(new Point(i, j));
            }
        }
        len = pizza.size();
        combi = new int[m];
        T.DFS(0, 0);
        System.out.println(answer);

    }
}

 

 

<문제의 핵심>

 

이 문제의 핵심은 결국 조합의 알고리즘을 알고 있느냐? 이다.

 

그것 외에는 정말 쉽게 생각하면 된다.

 

우선 ArrayList에 집과 피자 집을 넣어둔다.

 

거기서 조합을 구하여 조합 경우의 수 활용한다. 이때 DFS 성질을 이용한다.

 

 

DFS 성질

    private void DFS(int L, int s) {
        if (L == m) {

            for(int x : combi) System.out.print(x + " ");
            System.out.println();
//            int sum = 0;
//            for (Point h : house) {
//                int dis = Integer.MAX_VALUE;
//                for (int i : combi) {
//                    dis = Math.min(dis, Math.abs(h.x - pizza.get(i).x) + Math.abs(h.y - pizza.get(i).y));
//                }
//                sum += dis;
//            }
//            answer = Math.min(answer, sum);
        }
        else {
            for (int i = s; i < len; i++) {
                combi[L] = i;
                DFS(L+1, i+1);
            }
        }
    }

 

위의 알고리즘과 같이 조합에서의 DFS는 L과 s를 활용해서 진행한다.

 

이때 L 은 뽑고자하는 갯수의 인덱스이고

s는 시작점이라고 보면된다. 

 

이 조합의 DFS의 형태는 암기해 두고 두고두고 사용하자.

 

한 번 더 풀어보면서 더욱 잘 접근할 수 있도록 연습해보자