15686번: 치킨 배달
크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다. 이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는
www.acmicpc.net
이 문제는 도시 좌표 전체를 배열에 담을 필요 없이 치킨집(2)과 가정집(1) 좌표만 골라서 따로 선언한 배열에 담아주면 쉽게 풀 수 있다.
치킨집 배열에서 M개 치킨집을 살리는 경우를 구한다음, 모든 경우에 따른 치킨거리를 계산하여 최솟값을 출력하면 원하는 결과를 얻을 수 있다.
|
#include <iostream>
#include <cstdlib>
#include <vector>
using namespace std;
const int INF = 987654321;
vector<pair<int, int>> housePos;
vector<pair<int, int>> chickenPos;
vector<int> ckPick;
int ckCnt;
int bestCityDist = INF;
int min(int a, int b) { return a < b ? a : b; }
void ChickenDistance()
{
int houseLen = housePos.size();
int cityDist = 0;
for (int i = 0; i < houseLen; i++)
{
int minDistance = INF;
for (int j = 0; j < ckCnt; j++)
{
int yDist = abs(housePos[i].first - chickenPos[ckPick[j]].first);
int xDist = abs(housePos[i].second - chickenPos[ckPick[j]].second);
minDistance = min(minDistance, yDist + xDist);
}
cityDist += minDistance;
}
bestCityDist = min(bestCityDist, cityDist);
}
void Solution(int start, int pick)
{
if (pick == ckCnt)
{
ChickenDistance();
return;
}
int ckLen = chickenPos.size();
for (int i = start; i < ckLen; i++)
{
ckPick.push_back(i);
Solution(i + 1, pick+1);
ckPick.pop_back();
}
}
int main(void)
{
int maxLen;
cin >> maxLen >> ckCnt;
for (int i = 0; i < maxLen; i++)
for (int j = 0; j < maxLen; j++)
{
int n;
cin >> n;
if(n==1)housePos.push_back(pair<int, int>(i, j));
if(n==2)chickenPos.push_back(pair<int,int>(i, j));
}
Solution(0, 0);
cout << bestCityDist << endl;
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
알고리즘 200일 프로젝트 - 10day
내일도 열심히!
'알고리즘 > BOJ' 카테고리의 다른 글
| 백준 15683번: 감시 (C++) (0) | 2020.04.18 |
|---|---|
| 백준 1065번: 한수 (0) | 2020.04.17 |
| 백준 14500번: 테트로미노 (C++) (0) | 2020.04.15 |
| 백준 14889번: 스타트와 링크 (0) | 2020.04.14 |
| 백준 1018번: 체스판 다시 칠하기 (0) | 2020.04.13 |