문제 정보
백준 ( BOJ ) 17286번 유미
문제 풀이 : 완전탐색 OR 최단거리
문제 출처 : 경찰대학 > 2019 ChickenReallyGood 대회 D번
문제 풀이
이 문제는 2가지 방법으로 풀 수 가 있습니다.
첫번째 방법으로는 최단거리를 구하는 알고리즘이고
두번째 방법은 완전탐색을 이용하는 방법입니다.
저는 두번째 방법을 이용하여 풀었습니다.
만약 이 문제에서 사람의 수가 정해져 있지 않고, 더 많아질 수 있다면
당연히 최단거리 방법을 풀어야 합니다.
완전 탐색의 경우, 사람의 수가 많아 질 수록 급격하게 경우의 수가 늘어나
결국 시간초과를 야기 하기 때문입니다.
일반적으로 이렇게 수가 적으면 완전 탐색이 짜는데 더 빠르기 때문에
완전 탐색으로 짰습니다.
A , B , C , D 가 있고,
A가 유미, 나머지 B,C,D 가 사람입니다.
B , C, D 중 하나를 방문하고, 방문 해야 하는 목록에서 방문 한 것을 지우고,
그다음 방문 해야할 곳을 방문 합니다.
void find(int count, vector<int> & visit,int present, double cost) {
if (count == 3) {
pq.push(cost);
}
else {
for (int i = 1; i < 4; i++) {
if (visit[i] == 0) {
visit[i] = 1;
find(count + 1, visit, i, cost + cal(present, i));
visit[i] = 0;
}
}
}
}
이것을 이렇게 재귀로 돌려주시면 완전 탐색이 됩니다.
저같은 경우에는 제곱과, cost 계산을 함수로 만들어서 사용했습니다.
int doubles(int a) {
return a*a;
}
double cal(int a, int b) {
return sqrt(doubles(point[b].first - point[a].first) + doubles(point[b].second - point[a].second));
}
그리고, 이 문제에서 유의해야 할 점이 있는데,
답을 소수점을 뺴고 제출 해야 합니다.
저도 한번 실수 했었는데, 그래서 아예 int 로 계산을 했는데
중간 소수점이 다 삭제됨으로, 꼭 중간에는 다 double 로 계산 후
합치고 나서 int 로 잘라서 제출 해주세요.
저는 완전 탐색을 하면서, 최단 거리를 구하기 위해서
priority_queue 를 사용 하였습니다.
priority_queue<int, vector<int>, greater<int>> pq;
정렬 할 필요 없이 빠르게 최소값만 알아 낼 수 있거든요.
물론 최소값 비교연산 하는 것을 사용하거나,
다른 것을 사용해도 충분 합니다.
코드
#include <iostream>
#include <vector>
#include <cmath>
#include <queue>
#include <functional>
using namespace std;
vector<pair<int, int>> point (4);
priority_queue<int, vector<int>, greater<int>> pq;
int doubles(int a) {
return a*a;
}
double cal(int a, int b) {
return sqrt(doubles(point[b].first - point[a].first) + doubles(point[b].second - point[a].second));
}
void find(int count, vector<int> & visit,int present, double cost) {
if (count == 3) {
pq.push(cost);
}
else {
for (int i = 1; i < 4; i++) {
if (visit[i] == 0) {
visit[i] = 1;
find(count + 1, visit, i, cost + cal(present, i));
visit[i] = 0;
}
}
}
}
int main() {
int tempa, tempb;
for (int i = 0; i < 4; i++) {
cin >> tempa >> tempb;
point[i] = make_pair(tempa, tempb);
}
vector<int> visit(4, 0);
visit[0] = 1;
find(0, visit, 0, 0);
cout << pq.top();
}