백준 15685번 - 치킨 배달

구현 방법

치킨 집을 골라 도시의 치킨 거리를 구하는 단순한 문제이다. 치킨 집을 고르는 문제로 조합이다.

모든 가능한 상태(2진법)에 대해서

1. 해당 상태가 일단 M개 이하의 치킨집인지 확인

2. 치킨 거리 계산

으로 알고리즘이 이루어진다.

 

근데, 해당 문제를 재귀 방식의 조합으로 했을 때 시간 초과 혹은 메모리 초과가 발생하는 것을 확인할 수 있었다. 개발 언어가 c++ 이 아닌 java 인 점과 재귀(스택 메모리 처리) 라는 점에 의해서 해당 문제가 발생한다.

 

해당 문제의 시간 복잡도를 보면은

최악의 경우 2^13(모든 가능한 상태) * 13(치킨 집) * 집(100) 인 것을 확인할 수 있고 실제로 상태 검사를 통해 제외되는 상태가 있으니 이것보다는 작을 것이다. 먼저, 치킨 집을 고르는 행위를 수행한다면 13Cm  * 13 * 100 만의 시간 안에 해결할 수 있다.

 

코드

package simulation;

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

public class BJ15686{
    private static int N, M;
    private static int[][] map;
    private static List<Point> house = new ArrayList<>();
    private static List<Point> chickens = new ArrayList<>();
    private static int[] chickenDistances;
    private static int result = 100 * 2 * 50 * 13;

    public static void main(String[] args) throws IOException{
        readInput();
        solve2();
    }    

    private static void readInput() throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new int[N][N];

        for(int i = 0; i < N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < N; j++){
                map[i][j] = Integer.parseInt(st.nextToken());
                if(map[i][j] == 2){
                    chickens.add(new Point(i, j));
                }
                else if(map[i][j] == 1){
                    house.add(new Point(i, j));
                }
            }
        }

        chickenDistances = new int[house.size()];
    }

    private static void solve(){
        for(int status = 0; status < (1 << chickens.size()); status++){
            if(!checkStatus(status)) continue;

            for(int i = 0; i < house.size(); i++){
                chickenDistances[i] = 100;
            }

            int temp = status;
            for(int i = 0; i < chickens.size(); i++){
                int isSelected = temp % 2;
                temp /= 2;

                if(isSelected == 1){
                    for(int j = 0; j < house.size(); j++){
                        Point housePoint = house.get(j);
                        Point chickenPoint = chickens.get(i);
                        chickenDistances[j] = Math.min(chickenDistances[j], getChickenDistance(housePoint, chickenPoint));
                    }
                }
            }
            result = Math.min(result, getChickenDistanceOfCity(chickenDistances));
        }

        System.out.println(result);
    }

    private static boolean checkStatus(int status){
        int cnt = 0;
        for(int i = 0; i < 13; i++){
            int isSelected = status % 2;
            status /= 2;
            if(isSelected == 1) cnt++;
        }
        return cnt <= M;
    }

    private static int getChickenDistance(Point p1, Point p2){
        return (Math.max(p1.x, p2.x) - Math.min(p1.x, p2.x)) + (Math.max(p1.y, p2.y) - Math.min(p1.y, p2.y));
    }

    private static int getChickenDistanceOfCity(int[] chickenDistances){
        int sum = 0;
        for(int i = 0; i < house.size(); i++){
            sum += chickenDistances[i];
        }
        return sum;
    }

    static class Point{
        int x;
        int y;

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

결과