백준 15686번 치킨배달 (C++,Java) 풀이

백준 15686번 치킨배달 (C++,Java) 풀이

문제 설명

크기가 NxN 도시가 주어지며 칸의크기는 1x1이다. 도시의 각 칸은 빈칸,집,치킨집으로 구성되어있다.

이 도시의 치킨집은 모두 같은 프랜차이즈로 본사에서 수익을 증가시키기 위해 일부 치킨집을 폐업
시키려고 한다.도시에서 가장 수익을 많이 낼 수 있는 치킨집의 개수는 최대 M개이다.

치킨거리는 집과 가장 가까운 치킨집 사이의 거리이고, 각각의 집은 치킨 거리를 가지고 있으며,
도시의 치킨 거리는 모든 집의 치킨 거리의 합이다.

이때 치킨집 중에서 최대 M개를 고르는데 이때 도시의 치킨거리가 가장 작게 될지 구하시오.

1	0	0
0	2	0
0	0	2

위의 표를 예시로 치킨거리를 구해보자면 (1,1)에 위치한 집과 (2,2),(3,3)에 위치한 치킨집 2개가 있다.

이 때 각각의 치킨 거리를 구해보자면 |1-2| + |1-2| = 2, |1-3| + |1-3| = 4로 (1,1)의 위치한 집의 치킨거리는 2이다.

풀이

1. 도시에 있는 치킨집 중 M개를 고른다.

2. 각각의 집별로 M개의 치킨집의 치킨거리의 합을 구한다.

3. 이 때 최소의 도시의 치킨 거리를 구한다.

void dfs(int idx ,int m_cnt){
    if(m_cnt == m){
        int dist_sum = 0;
        for(int i = 0; i < house_pos.size(); i++){
            int dist_min = 65536;
            for(int j = 0; j < chick_pos.size(); j++){
                if(selected[j]){
                    dist_min = min(dist_min,getDist(house_pos[i],chick_pos[j]));
                }
            }
            dist_sum += dist_min;
        }
        answer = min(answer,dist_sum);
        return;
    }

    for(int i = idx; i < chick_pos.size(); i++){
        if(!selected[i]){
            selected[i] = true;
            dfs(i,m_cnt+1);
            selected[i] = false;
        }
    }
}

M개의 치킨집이 선택되기 전까지는 해당 치킨집이 선택되었는지 안되었는지 확인 한 후에 선택한다.
치킨집이 M개가 선택된다면 도시의 치킨거리를 구한다.

C++ 전체 소스코드
Java 소스코드 전체