개요

백준 10473번: 인간 대포

• 입력
  입력은 한 개의 길찾기 문제를 표현한다. 첫 줄에는 두 개의 실수가 입력되며 각각은 당신이 현재 위치한 X, Y좌표이다. 두 번째 줄에는 목적지의 X, Y좌표가 실수로 입력된다. 이어지는 줄에는 대포의 숫자 정수 n이 주어진다. 남은 n줄에는 한 줄에 대포 하나의 위치 정보가 주어지며, 이는 실수로 주어지는 X, Y 좌표이다. 모든 좌표는 미터로 측정되었으며 n의 값은 0 이상 100 이하이다. 입력으로 주어지는 모든 X, Y좌표는 0 이상 500 이하의 실수이고, 소수점 아래로 최대 두 자리까지만 주어진다.

• 출력
  한 줄에 걸쳐 목적지에 다다르기 위해 가장 빠른 시간을 출력하라. 실제 답과 0.001초 미만의 차이는 정답으로 인정한다.

접근 방식

1. 처음에 접근자체를 좌표계산으로 했다.

• 두 좌표 사이 거리 구하는 함수

  double GetDistance(pair<double,double>a, pair<double,double> b) {
  	return sqrt((a.first - b.first)*(a.first - b.first) +( a.second - b.second)* (a.second - b.second));
  }

• 두 좌표 사이에서 걸었을 경우의 시간 구하는 함수

  double GetRunningTime(pair<double, double> startLoc, pair<double, double> targetLoc) {
  	double dist = GetDistance(startLoc, targetLoc);
  	return dist / 5;
  }

• 두 좌표사이에서 대포를 탈 수 있을 때 최단 시간 구하는 함수

  double GetCannonLaunchTime(pair<double, double> startLoc, pair<double, double> targetLoc) {
  	double retTime = 2;
  	double dist = GetDistance(startLoc, targetLoc);
  	pair<double, double> afterUsingCannonLoc = { (targetLoc.first - startLoc.first) / dist * 50,
  		(targetLoc.second - startLoc.second) / dist * 50};
  	retTime+=GetRunningTime(afterUsingCannonLoc, targetLoc);
  	retTime = retTime> dist /5 ? dist / 5 : retTime;
  	return retTime;
  }

  대포 탔을 때는 sin^2 세타 + cos^2 세타= 1 을 이용하여
  startLoc에서 targetLoc방향으로 거리가 50인 좌표를 구했다.
  중요한 부분은 무조건 대포를 이용하는 게 아니다!!
  대포 이용하고 나머지 거리를 걷는 시간보다 그냥 걸어가는게 더 빠를수도 있다.

  따라서 해당 좌표에서 남은 거리만큼 걸어간 시간 + 대포 이용한 시간 2초
  와 startLoc에서 targetLoc으로 걸어간 시간을 비교해서 더 작은 값을 반환하도록 짰다

2. 이 함수에 아무 값이나 넣고 정확히 50을 반환하는지 실험을 하였는데 48.~ 이런식으로 50이 안 나와서 결국 다른 풀이를 검색을 하였다.

3. 찾아보니 이렇게 좌표로 정밀하게 계산할 필요없이 ,
   좌표끼리의 거리만 계산하고 해당 거리에서 50을 빼면 남은 거리가 나온다,,, 이 단순한걸 .. 충격적이다,,

   double GetCannonLaunchTime(pair<double, double> startLoc, pair<double, double> targetLoc) {
   	double retTime = 2;
   	double dist = GetDistance(startLoc, targetLoc);
   	retTime += fabs(dist - 50) / walkSpeed;
   	//걸어가는 시간과 대포타는 시간 비교
   	retTime = retTime> dist / walkSpeed? dist/walkSpeed : retTime;
   	return retTime;
   	}

4. 일단 모든 좌표들의 최단 시간은 걸어서 해당 좌표로 이동했을때의 시간으로 초기화한다.
   또한 최단시간 배열 minTime은
   0번 인덱스에 시작노드로의 최단시간을 저장한다.
   1번부터 각 대포의 위치로의 최단시간을 저장한다.
   따라서 대포갯수+1 인덱스의 저장된 최단시간이 답이 된다.

5. 각 지점끼리 연결된 간선이 따로 없으므로 다익스트라 알고리즘을 사용할 때,
   우선순위 큐에 top에 해당하는 좌표에서 나머지 모든 좌표로 진행을 하고,
   갱신을 해줬다.

   	//curnode위치에서 나머지 모든 대포의 위치로 진행 
   	for (int i = 1; i <= cannonAmount; i++) {
   		//자기 자신이라면 continue
   		if (i == curNode) continue;
   		//갱신해줘야 한다면 갱신
   		else if (minTime[i] > minTime[curNode] + GetCannonLaunchTime(adj[curNode], adj[i])) {
   			minTime[i] = minTime[curNode] + GetCannonLaunchTime(adj[curNode], adj[i]);
   			pq.push({ minTime[i], i });
   		}		}
   	//도착지점에서는 다른곳으로 갈 이유가 없으므로 우선순위큐에 푸시를 안해줌
   	if (minTime[cannonAmount + 1] > minTime[curNode] + GetCannonLaunchTime(adj[curNode], { targetX,targetY })) {
   				minTime[cannonAmount + 1] = minTime[curNode] + GetCannonLaunchTime(adj[curNode], { targetX,targetY });
   	}

전체 코드

	#include<iostream>
	#include<math.h>
	#include<vector>
	#include<queue>
	using namespace std;

	double startX, startY, targetX,targetY;
	int cannonAmount;
	const double walkSpeed = 5.0;
	//index번째 대포의 위치 pair형태로
	vector<pair<double, double>> adj;
	//pair의 first는 second에 대항하는 좌표로 걸리는 시간, second는 adj의 인덱스(0번은 원래 위치, 1~N은 대포순서 , N+1이 목적지.)
	priority_queue<pair<double, double>, vector<pair<double, double>>, greater<pair<double, double>>> pq;

	//0번은 원래 위치, 1~N은 대포순서 , N+1이 목적지.
	double minTime[102];
	//다익스트라에서 사용될 방문여부 저장용 bool형 배열
	bool visited[102];

	double GetDistance(pair<double,double>a, pair<double,double> b) {
		return sqrt((a.first - b.first)*(a.first - b.first) +( a.second - b.second)* (a.second - b.second));
	}

	double GetRunningTime(pair<double, double> startLoc, pair<double, double> targetLoc) {
		double dist = GetDistance(startLoc, targetLoc);
		return dist /walkSpeed;
	}

	double GetCannonLaunchTime(pair<double, double> startLoc, pair<double, double> targetLoc) {
		double retTime = 2;
		double dist = GetDistance(startLoc, targetLoc);
		retTime += fabs(dist - 50) / walkSpeed;
		//걸어가는 시간과 대포타는 시간 비교
		retTime = retTime> dist / walkSpeed? dist/walkSpeed : retTime;
		return retTime;
	}

	void Input() {
		double tmpCannonX = 0, tmpCannonY = 0;
		cin >> startX >> startY;
		cin >> targetX >> targetY;
		cin >> cannonAmount;
		//1번부터 대포사용하기 위해 0번에 시작좌표 푸시
		adj.push_back({ startX,startY });
		//1번부터 cannonAmount번 index까지 대포의 좌표 저장
		for (int i = 0; i < cannonAmount; i++) {
			cin >> tmpCannonX >> tmpCannonY;
			adj.push_back({ tmpCannonX, tmpCannonY });
		}
		//마지막에 목적지 좌표 저장
		adj.push_back({ targetX, targetY });
		fill(visited, visited + 100, false);
		minTime[0]=0;
		for (int i = 1; i <= cannonAmount+1; i++) {
			minTime[i] = GetRunningTime(adj[0], adj[i]);
			pq.push({ minTime[i],i });
		}
	}

	void Solution() {

		//시작점에서 제일 가까운 대포부터 다익스트라 시작
		while (!pq.empty()) {
			int curNode = 0;
			do {
				curNode = pq.top().second;
				pq.pop();
			} while (!pq.empty() && visited[curNode]);

			visited[curNode] = true;

			//curnode위치에서 나머지 모든 대포의 위치로 진행 
			for (int i = 1; i <= cannonAmount; i++) {
				//자기 자신이라면 continue
				if (i == curNode) continue;
				//갱신해줘야 한다면 갱신
				else if (minTime[i] > minTime[curNode] + GetCannonLaunchTime(adj[curNode], adj[i])) {
					minTime[i] = minTime[curNode] + GetCannonLaunchTime(adj[curNode], adj[i]);
					pq.push({ minTime[i], i });
				}
			}
			//도착지점에서는 다른곳으로 갈 이유가 없으므로 우선순위큐에 푸시를 안해줌
			if (minTime[cannonAmount + 1] > minTime[curNode] + GetCannonLaunchTime(adj[curNode], { targetX,targetY })) {
				minTime[cannonAmount + 1] = minTime[curNode] + GetCannonLaunchTime(adj[curNode], { targetX,targetY });
			}
		}
		cout.precision(6);
		cout<<fixed << minTime[cannonAmount + 1];
	}

	int main() {
		ios_base::sync_with_stdio(0);
		cin.tie(0);
		Input();
		Solution();

	}

문풀후생

처음에 풀었던 방식은 시작 좌표에서 제일 가까운 대포로 걸어가서
해당 대포에서 다익스트라를 시작했다.

하지만 예제는 맞지만 틀렸습니다가 떠서
반례 생각하느라 시간을 쏟으니 멘탈이 나가서 더 집중도 안 되었다.

하루 지나고 다시 들여다 보니, 제일 가까운 대포가
제일 가까운 대포 ㅡ 시작점 ㅡ 목적지점
이런식으로 반대편에 있을 경우도 있는데 생각을 못한 것이였다..

따라서 시작점에서 모든 좌표로의 걸어서 간 시간을 전부 우선순위 큐에 넣고
진행했더니 맞았다.