문제

BOJ 15686, 치킨배달

핵심

• 입력의 크기가 작아 구현에 초점을 맞춘다.
• 집과 치킨집이 주어진다. 주어진 치킨집에서 k개를 골랐을 때 모든 집과 치킨집 사이 거리의 최솟값을 구해야 한다.
• 크게 두 부분으로 나눌 수 있다. 첫째로 전체 치킨집 n개에서 k개를 골랐을 때 가능한 모든 경우의 수(조합)를 구해야 한다. 이는 dfs(완전탐색)을 통해 구할 수 있다. start 변수를 두어 중복을 제거했다.

void dfs(int depth, int start, vector<pair<int, int>>& seq, vector<bool>& isVisited) {
	if (depth == m) {
		// 전체 치킨집 중 m개를 골랐을 때
		return; 
	}
	for (int i = start; i < (int)chick.size(); ++i) {
		if (isVisited[i])
			continue;
		isVisited[i] = true;
		seq.push_back(chick[i]);
		dfs(depth + 1, i + 1,  seq, isVisited);
		isVisited[i] = false;
		seq.pop_back();
	}
}

• 가능한 치킨집을 골랐으면, 집들과 가장 가까운 치킨집을 고르기 위해 각각의 집에서 치킨집까지의 거리의 합을 구해야 한다. 거리는 치킨집에서 집까지의 y좌표, x좌표를 각각 차감하여 더해준 것으로 구할 수 있다. 모든 조합에서 최소 거리를 구하면 된다.

int sum = 0;
for (auto h : house) {
	int minChickDist = 1e9;
	for (auto c : seq)
		minChickDist = min(minChickDist, abs(c.first - h.first) + abs(c.second - h.second));
	sum += minChickDist;
}
ans = min(ans, sum);

개선

코드

시간복잡도

• $O(C(n, k)\times h \times c$)

C++

#include <iostream>
#include <vector>
using namespace std;

vector<pair<int, int>> house;
vector<pair<int, int>> chick;
int n, m;
int ans = 1e9;
void dfs(int depth, int start, vector<pair<int, int>>& seq, vector<bool>& isVisited) {
	if (depth == m) {
		int sum = 0;
		for (auto h : house) {
			int minChickDist = 1e9;
			for (auto c : seq)
				minChickDist = min(minChickDist, abs(c.first - h.first) + abs(c.second - h.second));
			sum += minChickDist;	
		}
		ans = min(ans, sum);
		return; 
	}
	for (int i = start; i < (int)chick.size(); ++i) {
		if (isVisited[i])
			continue;
		isVisited[i] = true;
		seq.push_back(chick[i]);
		dfs(depth + 1, i + 1,  seq, isVisited);
		isVisited[i] = false;
		seq.pop_back();
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			int num; 
			cin >> num;
			if (num == 1)
				house.push_back({i, j});
			else if (num == 2)
				chick.push_back({i, j});
		}
	}
	vector<pair<int, int>> seq;
	vector<bool> isVisited(chick.size(), false);
	dfs(0, 0, seq, isVisited);
	cout << ans;
}

Java

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

public class Main {
    static ArrayList<int[]> house = new ArrayList<>();
    static ArrayList<int[]> chick = new ArrayList<>();
    static int n, m;
    static int ans = Integer.MAX_VALUE;
    public static void main(String[] args) 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());
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                int num = Integer.parseInt(st.nextToken());
                if (num == 1)
                    house.add(new int[]{i, j});
                else if (num == 2)
                    chick.add(new int[]{i, j});
            }
        }
        boolean[] isVisited = new boolean[chick.size()];
        dfs(0, 0, new ArrayList<>(), isVisited);
        System.out.println(ans);
        br.close();
    }

    static void dfs(int depth, int start, ArrayList<int[]> seq, boolean[] isVisited) {
        if (depth == m) {
            int sum = 0;
            for (var h : house) {
                int minChickDist = Integer.MAX_VALUE;
                for (var c : seq)
                    minChickDist = Math.min(minChickDist, Math.abs(c[0] - h[0]) + Math.abs(c[1] - h[1]));
                sum += minChickDist;
            }
            ans = Math.min(ans, sum);
            return;
        }
        for (int i = start; i < chick.size(); ++i) {
            if (isVisited[i])
                continue;
            isVisited[i] = true;
            seq.add(chick.get(i));
            dfs(depth + 1, i + 1, seq, isVisited);
            isVisited[i] = false;
            seq.remove(seq.size() - 1);
        }
    }
}