득이공간
[백준 C++] 15686 치킨 배달 - 브루트포스 본문
#include <iostream>
using namespace std;
typedef pair<int, int> location;
int N, M, H, C;
location House[100];
location Chicken[13];
bool Check[13];
int Min = 1000000000;
int GetChickenDistance()
{
int Sum = 0;
for (int h = 0; h < H; ++h)
{
int Distance = 1000000000;
for (int c = 0; c < C; ++c)
{
if (!Check[c])
{
continue;
}
int X = abs(Chicken[c].second - House[h].second);
int Y = abs(Chicken[c].first - House[h].first);
Distance = min(Distance, X + Y);
}
Sum += Distance;
}
return Sum;
}
void DFS(int CurNum, int CurIdx)
{
if (CurNum == M)
{
Min = min(Min, GetChickenDistance());
return;
}
if (CurIdx == C)
{
return;
}
Check[CurIdx] = true;
DFS(CurNum + 1, CurIdx + 1);
Check[CurIdx] = false;
DFS(CurNum, CurIdx + 1);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.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[H] = location(i, j);
++H;
}
else if (Num == 2)
{
Chicken[C] = location(i, j);
++C;
}
}
}
DFS(0, 0);
cout << Min;
}
깊이 우선 & 완전 탐색으로 풀었습니다.
풀이 과정은 다음과 같습니다.
1. 각 집과 치킨집의 위치를 모두 저장
2. 주어진 수 만큼 치킨집을 선택하는 경우를 모두 탐색
3. 각각의 경우 중 치킨거리가 최소가 되는 값을 선택
'PS > 알고리즘 문제풀이' 카테고리의 다른 글
[백준 C++] 17070 파이프 옮기기 1 - 다이나믹프로그래밍 (0) | 2024.03.04 |
---|---|
[백준 C++] 15649 N과 M (1) - 백트래킹 (0) | 2024.03.04 |
[백준 C++] 12865 평범한 배낭 - 다이나믹프로그래밍 (0) | 2024.03.03 |
[백준 C++] 5639 이진 검색 트리 - 트리 (0) | 2024.02.29 |
[백준 C++] 2096 내려가기 - 다이나믹프로그래밍 (0) | 2024.02.29 |