[BOJ] 백준 15686 치킨 배달 간단한설명과 코드 C++

28 Mar 2020

Reading time ~2 minutes

문제 정보

백준 ( BOJ ) 15686 치킨 배달

문제 풀이 : dfs

문제 출처 : https://www.acmicpc.net/problem/15686

시작 Thinking

언뜻 보면, bfs로 최소 거리를 구해야 할 것 처럼 생긴 문제이다.

그러나 이 문제에서는 방해 되는 공간이 없다.

즉, 치킨집과 집과의 거리는 단순 계산으로, 좌표 차이점만 구하면 할 수 있다.

만약에 걸림돌(가로막힌길)이 있는 문제라면,

각 치킨집과 집의 거리를 먼저 bfs로 구해주고 시작 해야 한다.

근데 이 문제는 걸림돌이 없음으로 상당히 쉬워진다.

치킨집을 먼저 선택해서, 최소값을 비교 해 나가면 된다.

코드

#include <iostream>
#include <vector>


using namespace std;

int n, m;
int result = 2100000000; 
vector<vector<int>> load;
vector<pair<int, int>> house;
vector<pair<int, int>> chicken;
vector<pair<int, int>> toFind;
int calLen(int ax, int ay, int bx, int by) {
	return (abs(ax - bx) + abs(ay - by));
}
void calIsMin() {
	int min = 21000;
	int tempResult = 0; 
	int temp;
	for (int i = 0; i < house.size(); i++) {
		min = 21000;
		for (int j = 0; j < toFind.size(); j++) {
			temp = calLen(house[i].first, house[i].second, toFind[j].first, toFind[j].second);
			if (min > temp)
				min = temp;
		}
		tempResult += min;
	}
	if (tempResult < result)
		result = tempResult;
}
void fun(int start, int count) {
	if (count != m) {
		for (int i = start; i < chicken.size(); i++) {
			toFind[count] = chicken[i];
			fun(i + 1, count + 1);
		}
	}
	else {
		/*
		for (int i = 0; i < m; i++) {
			cout << toFind[i].second << " , " << toFind[i].first << " ";
		}
		cout << endl;*/
		calIsMin();
	}
}
int main() {
	int temp;
	cin >> n >> m;
	load.assign(n, vector<int>(n, 0));
	toFind.assign(m,make_pair(0,0));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> temp;
			load[i][j] = temp;
			if (temp == 1)
				house.push_back(make_pair(i, j));
			else if (temp == 2)
				chicken.push_back(make_pair(i,j));
		}
	}
	fun(0, 0);
	cout << result;
	return 0;
}

후기

알고리즘 생각 시간 : 11분 15초

구현 시간 : 18분 02초

백준 C++dfs