[Inflearn] 자바 알고리즘 문제풀이 #08-15 15. 피자 배달 거리(삼성 SW역량평가 기출문제 : DFS활용)

문제

설명

N×N 크기의 도시지도가 있습니다. 도시지도는 1×1크기의 격자칸으로 이루어져 있습니다.

각 격자칸에는 0은 빈칸, 1은 집, 2는 피자집으로 표현됩니다. 각 격자칸은 좌표(행번호, 열 번호)로 표현됩니다.

행번호는 1번부터 N번까지이고, 열 번호도 1부터 N까지입니다.

도시에는 각 집마다 “피자배달거리”가 았는데 각 집의 피자배달거리는 해당 집과 도시의 존재하는

피자집들과의 거리 중 최소값을 해당 집의 “피자배달거리”라고 한다.

집과 피자집의 피자배달거리는 |x1-x2|+|y1-y2| 이다.

예를 들어, 도시의 지도가 아래와 같다면

(1, 2)에 있는 집과 (2, 3)에 있는 피자집과의 피자 배달 거리는 |1-2| + |2-3| = 2가 된다.

최근 도시가 불경기에 접어들어 우후죽순 생겼던 피자집들이 파산하고 있습니다.

도시 시장은 도시에 있는 피자집 중 M개만 살리고 나머지는 보조금을 주고 폐업시키려고 합니다.

시장은 살리고자 하는 피자집 M개를 선택하는 기준으로 도시의 피자배달거리가 최소가 되는 M개의 피자집을 선택하려고 합니다.

도시의 피자 배달 거리는 각 집들의 피자 배달 거리를 합한 것을 말합니다.

 

입력 

첫째 줄에 N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 12)이 주어진다.

둘째 줄부터 도시 정보가 입력된다.

 

출력 

첫째 줄에 M개의 피자집이 선택되었을 때 도시의 최소 피자배달거리를 출력한다.

예시 입력 1 

4 4
0 1 2 0
1 0 2 1
0 2 1 2
2 0 1 2

예시 출력 1

6

 

 

 

내 풀이

import java.util.ArrayList;
import java.util.Scanner;
class Point {
    public int x, y;
    Point(int x, int y){
        this.x = x;
        this.y = y;
    }
}
public class Main8_15 {
    static int n, m;
    static ArrayList<Point> hs, pz;
    static int answer=Integer.MAX_VALUE;
    static Point[] combi;

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


    public static void main(String[] args) {
        Main8_15 T = new Main8_15();
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        hs = new ArrayList<>();
        pz = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int num = sc.nextInt();
                if(num == 1) hs.add(new Point(i, j)); //집
                else if(num == 2) pz.add(new Point(i, j)); //피자집
            }
        }
        combi = new Point[m];
        T.DFS(0, 0);
        System.out.println(answer);
    }
}

혼자서 1시간 동안 풀다가 답이 없어서 선생님 문제 설명을 듣고 다시 혼자 풀어봤다.

5개의 테스트 케이스 중 4개만 통과. 뭐지... 뭐가 잘못된 거지...?ㅠㅠㅠㅠ

 

--> 그 후 1시간 더 걸려 코드 완성

combi 배열을 계속 DFS()에서 초기화 해줬는데(DFS에서만 사용되니까) Main에서 용량을 할당 해줘야 알맞게 돌아갔다...

오래걸렸지만 그래두 이렇게 어려운 문제를 풀려고 노력했으니까 시간이 아깝진 않다. 뿌듯뿌듯 +1 +1

 

 

 

선생님 풀이

import java.util.ArrayList;
import java.util.Scanner;
class Point {
    public int x, y;
    Point(int x, int y){
        this.x = x;
        this.y = y;
    }
}

public class Main8_15 {
    static int n, m, len, answer=Integer.MAX_VALUE;
    static ArrayList<Point> hs, pz;
    static int[] combi;

    private void DFS(int L, int s) {
        if(L==m) {
            int sum=0;
            for(Point h : hs) {
                int dis=Integer.MAX_VALUE;
                for(int i : combi){
                    dis=Math.min(dis, Math.abs(h.x-pz.get(i).x)+Math.abs(h.y-pz.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) {
        Main8_15 T = new Main8_15();
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        hs = new ArrayList<>();
        pz = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int num = sc.nextInt();
                if(num == 1) hs.add(new Point(i, j)); //집
                else if(num == 2) pz.add(new Point(i, j)); //피자집
            }
        }
        len=pz.size();
        combi = new int[m];
        T.DFS(0, 0);
        System.out.println(answer);
    }
}

 

 

 

결과