[Algorithm] 99클럽 코테 스터디 15일차 TIL BOJ 15686

문제

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

풀이

문제 분석

• M개의 치킨집을 선택했을 때 도시의 치킨거리가 최소가 되는 시점을 구해야 한다
• M개의 치킨집의 순서는 상관 없으므로 순열이 아닌 "조합"을 고려해야 한다
• dfs를 사용하여 폐업하지 않은 치킨집의 개수가 M과 같아지는 시점에 탐색을 종료하고 각 집 별로 치킨 거리를 계산하여 도시의 치킨 거리를 최소값으로 업데이트한다

코드

import java.io.*;
import java.util.*;

class Point {
    public int x;
    public int y;

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


public class Main {
    private static int N;
    private static int M;
    private static boolean[] open;
    private static ArrayList<Point> chicken = new ArrayList<>();
    private static ArrayList<Point> house = new ArrayList<>();
    private static int minDistanceOfCity = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<N; j++) {
                int number = Integer.parseInt(st.nextToken());
                Point point  = new Point(i, j);
                if(number == 1) {
                    house.add(point);
                }
                else if(number == 2) {
                    chicken.add(point);
                }
            }
        }
        open = new boolean[chicken.size()];
        minDistanceOfCity = Integer.MAX_VALUE;
        dfs(0, 0);

        bw.write(String.valueOf(minDistanceOfCity));
        bw.flush();
        bw.close();
    }

    private static void dfs(int start, int count) {
        if(count == M) {
            int sumOfDistance = 0;

            for (int i=0; i<house.size(); i++) {
                int minDistanceOfHouse = Integer.MAX_VALUE;
                for (int j=0; j< chicken.size(); j++) {
                    if(open[j]) {
                        int distance = Math.abs(house.get(i).x - chicken.get(j).x) + Math.abs(house.get(i).y - chicken.get(j).y);
                        minDistanceOfHouse = Math.min(minDistanceOfHouse, distance);
                    }
                }
                sumOfDistance += minDistanceOfHouse;
            }
            minDistanceOfCity = Math.min(minDistanceOfCity, sumOfDistance);
            return;
        }

        for(int i=start; i< chicken.size();i++) {
            if(!open[i]) {
                open[i] = true;
                dfs(i+1, count+1);
                open[i] = false;
            }
        }
    }
}

TIL

• 처음에 조합이라는 것을 고려하지 않고 dfs의 start 인덱스를 설정하지 않았을 때 시간초과가 발생했다
• 처음에 작성한 코드는 다음과 같다

import java.io.*;
import java.util.*;


class Point {
    public int x;
    public int y;

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


public class Main {
    private static int N;
    private static int M;
    private static boolean[] open;
    private static ArrayList<Point> chicken = new ArrayList<>();
    private static ArrayList<Point> house = new ArrayList<>();
    private static int minDistanceOfCity = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<N; j++) {
                int number = Integer.parseInt(st.nextToken());
                Point point  = new Point(i, j);
                if(number == 1) {
                    house.add(point);
                }
                else if(number == 2) {
                    chicken.add(point);
                }
            }
        }
        open = new boolean[chicken.size()];
        minDistanceOfCity = Integer.MAX_VALUE;

        for (int i=0; i<chicken.size(); i++) {
            open[i] = true;
            dfs(1);
            open = new boolean[chicken.size()];
        }

        bw.write(String.valueOf(minDistanceOfCity));
        bw.flush();
        bw.close();
    }

    private static void dfs(int count) {
        if(count == M) {
            int sumOfDistance = 0;

            for (int i=0; i<house.size(); i++) {
                int minDistanceOfHouse = Integer.MAX_VALUE;
                for (int j=0; j< chicken.size(); j++) {
                    if(open[j]) {
                        int distance = Math.abs(house.get(i).x - chicken.get(j).x) + Math.abs(house.get(i).y - chicken.get(j).y);
                        minDistanceOfHouse = Math.min(minDistanceOfHouse, distance);
                    }
                }
                sumOfDistance += minDistanceOfHouse;
            }
            minDistanceOfCity = Math.min(minDistanceOfCity, sumOfDistance);
            return;
        }

        for(int i=0; i< chicken.size();i++) {
            if(!open[i]) {
                open[i] = true;
                dfs(count+1);
                open[i] = false;
            }
        }
    }
}

• 시간을 어떻게하면 더 줄일 수 있을까 생각해보니 start 변수를 사용하여 앞에서 선택에 포함되었던 치킨집은 제외할 수 있겠다는 생각이 들었다
• 기존의 코드는 1 - 2 - 3 이라는 탐색이 있다고할 때, 2 - 1 - 3 순서로 탐색하고 있었기 때문에 순서가 중요하지 않은 문제인데 더 많은 탐색을 진행하고 있었다
• 다음부터는 순서가 중요한 순열인지, N개중 M개를 단순히 선택하는 조합인지 구별하여 문제를 해결해야겠다는 생각이 들었다