[백준 15686/JAVA] 치킨 배달

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

15686번: 치킨 배달

문제를 보자마자 예전에 풀어본 브루트포스와 백트래킹을 이용해야하는 문제인 것을 알았다.

하지만 푼 지 오래되어 어떻게 하는지 까먹어버려 꽤 고생했다...

 

치킨집의 총 갯수를 C라고 한다면 C중 M개의 치킨집을 고르는 경우의 수를 모두 구해 각 거리를 구해 그 중 최소 거리를 찾으면 된다.

조합이라고 생각하면 편하다.

 

    static class Pair {
        Integer first;
        Integer second;

        public Pair(Integer first, Integer second) {
            this.first = first;
            this.second = second;
        }

        public Integer getFirst() {
            return first;
        }

        public Integer getSecond() {
            return second;
        }
    }

치킨집과 집을 Pair 형태로 저장하기 위한 클래스이다. first가 x, second가 y좌표이다. 자바에서 Pair를 제공한다고 하는데 되질 않아 그냥 직접 구현했다.

 

    public static void getSelect(int index, int count) {
        int distance;
        if (count == M) {
            distance = getDistance();
            if (result > distance)
                result = distance;
        } else {
            for (int i = index; i < chicken.size(); i++) {
                if (visit[i] == Boolean.FALSE) {
                    visit[i] = Boolean.TRUE;
                    getSelect(i, count + 1);
                    visit[i] = Boolean.FALSE;
                }
            }
        }
    }

치킨집을 고르는 함수이다. DFS방식을 이용했다. visit배열을 사용해 선택한 치킨집을 표시한다.

index는 현재 확인하는 배열의 index, count는 현재 몇 번째 치킨집인지 나타내는 변수이다.

현재 확인하는 치킨집을 visit 처리를 해준 후 다음 치킨집을 확인한다.

재귀 호출이 끝나면 다시 false 처리를 해주어 다시 원래대로 복구시켜준다.

 

예제 입력 2번을 통해 true false 처리가 어떻게 되는지 확인하면

빨간 밑줄을 보면 모든 경우의 수가 선택된다. 이를 이용해 거리를 구한다.

 

    public static int getDistance() {
        int totaldistance = 0;
//        for (int i = 0; i < visit.length; i++) {
//            System.out.print(visit[i] + " ");
//        }
        System.out.println();
        for (int i = 0; i < home.size(); i++) {
            int distance = Integer.MAX_VALUE, temp;
            for (int j = 0; j < chicken.size(); j++) {
                if (visit[j] == Boolean.TRUE) {
                    temp = Math.abs(home.get(i).getFirst() - chicken.get(j).getFirst())
                            + Math.abs(home.get(i).getSecond() - chicken.get(j).getSecond());
                    if (distance > temp) distance = temp;
                }
            }
            totaldistance += distance;
        }
        return totaldistance;
    }

거리를 구하는 함수이다. 각 집들과 선택된 치킨집들 사이의 거리를 구하며 그 중 최소거리를 구한다.

distance가 해당 집에서 가장 가까운 치킨집 사이의 거리이다.

이를 totaldistance에 더해준다.

이 totaldistance 중 최소 거리가 답이다.

반응형

 

전체코드

import java.util.Scanner;
import java.util.Vector;

public class Main {
    static int N, M, result = Integer.MAX_VALUE;
    static int[][] map;
    static Boolean[] visit;
    static Vector<Pair> home = new Vector<Pair>();
    static Vector<Pair> chicken = new Vector<Pair>();

    static class Pair {
        Integer first;
        Integer second;

        public Pair(Integer first, Integer second) {
            this.first = first;
            this.second = second;
        }

        public Integer getFirst() {
            return first;
        }

        public Integer getSecond() {
            return second;
        }
    }

    public static void getSelect(int index, int count) {
        int distance;
        if (count == M) {
            distance = getDistance();
            if (result > distance)
                result = distance;
        } else {
            for (int i = index; i < chicken.size(); i++) {
                if (visit[i] == Boolean.FALSE) {
                    visit[i] = Boolean.TRUE;
                    getSelect(i, count + 1);
                    visit[i] = Boolean.FALSE;
                }
            }
        }
    }

    public static int getDistance() {
        int totaldistance = 0;
//        for (int i = 0; i < visit.length; i++) {
//            System.out.print(visit[i] + " ");
//        }
        System.out.println();
        for (int i = 0; i < home.size(); i++) {
            int distance = Integer.MAX_VALUE, temp;
            for (int j = 0; j < chicken.size(); j++) {
                if (visit[j] == Boolean.TRUE) {
                    temp = Math.abs(home.get(i).getFirst() - chicken.get(j).getFirst())
                            + Math.abs(home.get(i).getSecond() - chicken.get(j).getSecond());
                    if (distance > temp) distance = temp;
                }
            }
            totaldistance += distance;
        }
        return totaldistance;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        map = new int[N][];

        for (int i = 0; i < N; i++) {
            map[i] = new int[N];
            for (int j = 0; j < N; j++) {
                map[i][j] = sc.nextInt();
                if (map[i][j] == 1) home.add(new Pair(i, j));
                else if (map[i][j] == 2) chicken.add(new Pair(i, j));
            }
        }
        visit = new Boolean[chicken.size()];

        for (int i = 0; i < visit.length; i++) {
            visit[i] = Boolean.FALSE;
        }

        getSelect(0, 0);
        System.out.println(result);
    }
}