Taxol

I’ve always been.

백준 15686 - 치킨 배달

Updated:

C++

15686 번 - 치킨 배달

문제

도시에 있는 치킨집 중에서 최대 M개를 고르고, 나머지 치킨집은 모두 폐업시켜야 한다. 어떻게 고르면, 도시의 치킨 거리가 가장 작게 될지 구하는 프로그램을 작성하시오.

문제 출처

접근 방법

  1. 먼저 모든 치킨집과 가정집을 vector<>에 좌표를 저장합니다.
  2. 이후 DFS를 이용하여 치킨집 m개를 선택합니다.
  3. 뽑은 치킨 집을 각 가정집과 거리를 하나씩 비교를 하여 제일 짧은 거리를 계산, 이를 도시 치킨 거리에 합한다.
  4. 가장 짧은 도시 치킨 거리를 도출해 내어 해결한다.

구현

Main()

치킨 집과 가정 집을 저장한다. 또한 visited도 치킨 집이 인식 될 때마다 false를 늘려준다.

selected 함수는 이후 뽑을 치킨 집 개수만큼 동적으로 배열을 할당한다.

DFS()

DFS를 통해 치킨집을 m개 만큼 뽑는다. 중복을 피하기 위해 idx 매개변수를 전달 해주어, (첫번째 치킨집, 두번째 치킨집) AND (두번째 치킨집, 첫번재 치킨집)과 같이 결과에는 영향을 주지 못하고 중복으로 인해 낭비되는 것을 방지한다.

Dtn()

뽑은 치킨 집과 모든 가정집의 거리 합의 최소값을 구하는 함수이다. 매개 변수로 앞서 뽑은 배열을 가진다. 각 집을 하나씩 for문으로 뽑는다. 이후 m개의 뽑은 치킨집의 거리를 비교하여, 가장 짧은 거리를 도출해 낸다. 이 거리를 city_dtn에 합쳐주어 도시의 치킨 거리를 구한다.

최종적으로 제일 작은 도시의 치킨 거리을 구한다!

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

#define MAX 987654321

int n, m;
int** city;
int result = MAX;
vector<pair<int, int>> chicken, house;
vector<bool> visited;

void DFS(int lv, int* s, int);
void Dtn(int* s);

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	cin >> m;
	city = new int* [n];
	for (int i = 0; i < n; i++) {
		city[i] = new int[n];
	}
	int temp = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> city[i][j];
			if (city[i][j] == 2) {
				chicken.push_back(make_pair(i, j));			// 치킨 집을 저장
				visited.push_back(false);
			}
			else if (city[i][j] == 1) {
				house.push_back(make_pair(i, j));			// 모든 집을 저장
			}
		}
	}
	int* selected;
	selected = new int[m];
	DFS(0, selected, 0);

	cout << result;
	return 0;
}
//치킨 집을 선택하는 DFS, M개가 선택되면 거리를 계산한다.
void DFS(int lv, int* s, int idx) {
	if (lv == m) {							//치킨집 m개를 선택하면 거리 계산으로 넘어감
		Dtn(s);
		return;
	}
	if (lv == chicken.size()) {				//기저, 치킨 집보다 뽑는 개수가 많은 것을 방지
		return;
	}
	int size = chicken.size();
	for (int i = idx; i < size; i++) {		//중복을 피하기 위한 idx
		if (!visited[i]) {
			visited[i] = true;
			s[lv] = i;						//치킨집을 선택
			DFS(lv + 1, s, i + 1);
			visited[i] = false;
		}
	}
}
//뽑은 치킨집과 집 사이의 거리를 구한다.
void Dtn(int* s) {
	int size = house.size();
	int hy, hx, cy, cx, city_dtn = 0;
	int ch_dtn = MAX;
	for (int i = 0; i < size; i++) {		//집 하나를 선택한다.
		hy = house.at(i).first;
		hx = house.at(i).second;
		for (int j = 0; j < m; j++) {		//뽑은 치킨 집을 위의 집과 비교를 하며, 제일 짧은 거리를 `도시의 치킨 거리`에 합한다.
			cy = chicken.at(s[j]).first;
			cx = chicken.at(s[j]).second;
			ch_dtn = min((abs(hy - cy) + abs(hx - cx)), ch_dtn);
		}
		city_dtn += ch_dtn;
		ch_dtn = MAX;
	}
	result = min(result, city_dtn);			//더 짧은 `도시의 치킨 거리`가 나오면 갱신한다.
}

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

public class Main {
	static int n, m, result = Integer.MAX_VALUE, c, h;
	static int[][] map;
	static int[] sel;
	static List<int[]> chick;
	static List<int[]> house;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer stk = new StringTokenizer(br.readLine());
    	
    	n = stoi(stk.nextToken());
    	m = stoi(stk.nextToken());
    	
    	map = new int[n][n];
    	chick = new ArrayList<>();
    	house = new ArrayList<>();
    	sel = new int[m];
    	
    	for(int i = 0; i < n; i++) {
    		stk = new StringTokenizer(br.readLine());
    		for(int j = 0; j < n; j++) {
    			map[i][j] = stoi(stk.nextToken());
    			if(map[i][j] == 2) {
    				chick.add(new int[] {i,j});
    				c++;
    			}
    			else if(map[i][j] == 1) {
    				house.add(new int[] {i,j});
    				h++;
    			}
    		}
    	}
    	
    	DFS(0,0);
    	
    	System.out.println(result);
    	br.close();
	}
	
	// m개의 치킨집을 뽑는 조합
	static void DFS(int lv, int st) {
		if(lv == m) {
			int sum = 0, hy, hx, cy, cx;
			// 집을 하나씩 선택하여 치킨 거리를 구한다.
			for(int i = 0; i < h; i++) {
				int dist = Integer.MAX_VALUE;
				
				hy = house.get(i)[0];
				hx = house.get(i)[1];
				
				for(int j = 0; j < m; j++) {
					cy = chick.get(sel[j])[0];
					cx = chick.get(sel[j])[1];
					
					// 여러 치킨집 중에서 현재 집까지 가장 짧은 것을 선택
					dist = Math.min(dist, calDist(hy, hx, cy, cx));
				}
				
				sum += dist;
			}
			
			result = Math.min(sum, result);
			return;
		}
		
		for(int i = st; i < c; i++) {
			sel[lv] = i;
			DFS(lv + 1, i + 1);
		}
	}
	
	static int calDist(int y1, int x1, int y2, int x2) {
		return Math.abs(y1 - y2) + Math.abs(x2 - x1);
	}
	
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

후기 및 개선할 점

후기:

잘 풀어 놓고, ch_dtn을 갱신 해 줄 때마다 999라는 적은 수로 초기화를 해주어 틀렸다.

이후 백준 질의응답 게시판을 통해 sait2000 분이 가르켜 주셔서 겨우 풀었다. 이제 최댓값을 아예 완전 큰 수로 define 하는 습관을 길러야겠다!

You may also enjoy