[백준] 치킨배달

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

15686번: 치킨 배달

 

 

전형적인 완탐문제이나, 무식하게 완탐하면 시간초과나

 

시간초과 코드

package algorithm.baekjoon.bj15686;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
    static int ans = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int[] input = Arrays.stream(br.readLine()
                .split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();

        int n = input[0];
        int m = input[1];

        int arr[][] = new int[n][n];

        //이차원 배열 만들기
        for (int i = 0; i < n; i++) {
            int[] line = Arrays.stream(br.readLine()
                    .split(" "))
                    .mapToInt(Integer::parseInt)
                    .toArray();

            for (int j = 0; j < line.length; j++) {
                arr[i][j] = line[j];
            }
        }

        List<Pair> homes = new ArrayList<>();
        List<Pair> chicken = new ArrayList<>();

        //집,치킨집 좌표 구한다
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length; j++) {
                if (arr[i][j] == 1) homes.add(new Pair(i, j, Integer.MAX_VALUE));
                else if (arr[i][j] == 2) chicken.add(new Pair(i, j, 0));
            }
        }
        boolean[] isVisited = new boolean[chicken.size()];
        choose(chicken, homes, m, isVisited, 0);

        System.out.println(ans);
    }

    private static void choose(List<Pair> chicken, List<Pair> homes, int m, boolean[] isVisited, int cnt) {
        if (m == cnt) {
            for (int i = 0; i < isVisited.length; i++) {
                if (isVisited[i]) {
                    Pair ch = chicken.get(i);
                    //집별 선택한 치킨집의 거리를 구해서 최소값인 경우 해당 거리 저장
                    for (Pair home : homes) {
                        home.calDist(ch);
                    }
                }
            }

            int sumDist = 0;
            for (Pair home : homes) {
                sumDist += home.dist;
                home.initDist();
            }
            ans = Math.min(ans, sumDist);
            return;
        }

        //치킨선택
        for (int i = 0; i < chicken.size(); i++) {
            if (!isVisited[i]) {
                isVisited[i] = true;
                choose(chicken, homes, m, isVisited, cnt + 1);
                isVisited[i] = false;
            }
        }
    }
}

class Pair {
    int y;
    int x;
    int dist;

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

    void calDist(Pair p) {
        int newDist = Math.abs(this.y - p.y) + Math.abs(this.x - p.x);
        this.dist = Math.min(this.dist, newDist);
    }

    void initDist() {
        this.dist = Integer.MAX_VALUE;
    }
}

 

통과한 코드

package algorithm.baekjoon.bj15686;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
    static int ans = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int[] input = Arrays.stream(br.readLine()
                .split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();

        int n = input[0];
        int m = input[1];

        int arr[][] = new int[n][n];

        //이차원 배열 만들기
        for (int i = 0; i < n; i++) {
            int[] line = Arrays.stream(br.readLine()
                    .split(" "))
                    .mapToInt(Integer::parseInt)
                    .toArray();

            for (int j = 0; j < line.length; j++) {
                arr[i][j] = line[j];
            }
        }

        List<Pair> homes = new ArrayList<>();
        List<Pair> chicken = new ArrayList<>();

        //집,치킨집 좌표 구한다
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length; j++) {
                if (arr[i][j] == 1) homes.add(new Pair(i, j, Integer.MAX_VALUE));
                else if (arr[i][j] == 2) chicken.add(new Pair(i, j, 0));
            }
        }
        boolean[] isVisited = new boolean[chicken.size()];
        choose(chicken, homes, m, isVisited, 0, 0);

        System.out.println(ans);
    }

    private static void choose(List<Pair> chicken, List<Pair> homes, int m, boolean[] isVisited, int cnt, int idx) {
        if (m == cnt) {
            for (int i = 0; i < isVisited.length; i++) {
                if (isVisited[i]) {
                    Pair ch = chicken.get(i);
                    //집별 선택한 치킨집의 거리를 구해서 최소값인 경우 해당 거리 저장
                    for (Pair home : homes) {
                        home.calDist(ch);
                    }
                }
            }

            int sumDist = 0;
            for (Pair home : homes) {
                sumDist += home.dist;
                home.initDist();
            }
            ans = Math.min(ans, sumDist);
            return;
        }

        //치킨선택
        for (int i = idx; i < chicken.size(); i++) {
            if (!isVisited[i]) {
                isVisited[i] = true;
                choose(chicken, homes, m, isVisited, cnt + 1, i + 1);
                isVisited[i] = false;
            }
        }
    }
}

class Pair {
    int y;
    int x;
    int dist;

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

    void calDist(Pair p) {
        int newDist = Math.abs(this.y - p.y) + Math.abs(this.x - p.x);
        this.dist = Math.min(this.dist, newDist);
    }

    void initDist() {
        this.dist = Integer.MAX_VALUE;
    }
}

 

 

차이를 잘 찾아보면, 치킨을 선택하는 반복문에서 시작 인덱스를 0부터하냐 이전에 선택한 다음의 인덱스부터 하냐의 차이임

 

0부터 하는 경우는, 선택하지 않은 치킨집을 순서와 상관없이 선택하다보니, 중복된 계산을 함

예로 3개를 선택한다할 경우, 0 1 2 / 0 2 1 / 1 0 2 / 1 2 0 .... 이렇게 순서를 정해서 계산 (모두 같은 결과값이지만..)하는 결과로 시간복잡도가 높아짐

 

즉, 순서를 정해서 1번만 선택하여 진행하면 중복된 계산이 없으므로 속도가 더 빠름