[C언어] 백준 10473번: 인간 대포

https://www.acmicpc.net/problem/10473

10473번: 인간 대포

 

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#pragma warning(disable:4996)
#define INF 101

typedef struct Position {
	double x, y;
} Position;

typedef struct Metadata {
	int n;
	Position* obj;
	double** graph;
} Metadata;

typedef struct Pair {
	int vIndex;
	double dist;
} Pair;

typedef struct PriortyQueue {
	int count;
	Pair* data;
} PriortyQueue;

Position scanPosition() {
	Position res;
	scanf("%lf %lf", &res.x, &res.y);
	return res;
}

double getDistance(Position p1, Position p2) {
	return sqrt(pow(p1.x - p2.x, 2) + pow(p1.y - p2.y, 2));
}

void swapItems(PriortyQueue* pq, int* locator, int index1, int index2) {
	locator[pq->data[index1].vIndex] = index2;
	locator[pq->data[index2].vIndex] = index1;

	Pair tmp = pq->data[index1];
	pq->data[index1] = pq->data[index2];
	pq->data[index2] = tmp;
}

void upheap(PriortyQueue* pq, int* locator, int index) {
	if (index <= 1) return;

	int parent = index / 2;
	if (pq->data[parent].dist <= pq->data[index].dist) return;

	swapItems(pq, locator, parent, index);
	upheap(pq, locator, parent);
}

void replaceKey(PriortyQueue* pq, int* locator, int index, double dist) {
	pq->data[index].dist = dist;
	upheap(pq, locator, index);
}

void downheap(PriortyQueue* pq, int* locator, int index) {
	if (index * 2 > pq->count) return;

	int child = index * 2;
	if (child + 1 <= pq->count && pq->data[child].dist > pq->data[child + 1].dist)
		child += 1;

	if (pq->data[index].dist <= pq->data[child].dist) return;

	swapItems(pq, locator, index, child);
	downheap(pq, locator, child);
}

Pair pop(PriortyQueue* pq, int* locator) {
	Pair res = pq->data[1];

	pq->data[1].dist = INF;
	swapItems(pq, locator, 1, pq->count);
	downheap(pq, locator, 1);
	pq->count -= 1;

	return res;
}

void doDijkstra(Metadata* mt) {
	int i;
	// dist
	double* dist = (double*)malloc(sizeof(double)*(mt->n+2));
	for (i = 1; i < mt->n + 2; i++) dist[i] = INF;
	dist[0] = 0;

	// 우선순위큐 초기화
	PriortyQueue* pq = (PriortyQueue*)malloc(sizeof(PriortyQueue));
	pq->count = mt->n + 2;
	pq->data = (Pair*)malloc(sizeof(Pair) * (mt->n + 3)); // 주의: 1-indexing
	int* locator = (int*)malloc(sizeof(int) * (mt->n + 2));
	for (i = 1; i < mt->n + 3; i++) {
		pq->data[i].dist = INF;
		pq->data[i].vIndex = i-1;
		locator[i - 1] = i;
	}
	replaceKey(pq, locator, locator[0], 0);

	// 다익스트라
	while (pq->count > 0) {
		Pair popped = pop(pq, locator);
		int vIndex = popped.vIndex;
		double d = popped.dist;

		for (i = 0; i < mt->n + 2; i++) {
			if (i != vIndex && dist[i] > d + mt->graph[vIndex][i]) {
				dist[i] = d + mt->graph[vIndex][i];
				replaceKey(pq, locator, locator[i], dist[i]);
			}
		}
	}
	
	printf("%f", dist[1]);

	// Free
	free(locator);
	free(pq->data);
	free(pq);
	free(dist);
}

int main() {
	int i, j;

	Metadata* mt = (Metadata*)malloc(sizeof(Metadata));

	Position a = scanPosition();
	Position b = scanPosition();

	scanf("%d", &mt->n);
	mt->obj = (Position*)malloc(sizeof(Position) * (mt->n+2));
	mt->obj[0] = a; mt->obj[1] = b;

	for (i = 2; i < mt->n+2; i++) {
		mt->obj[i] = scanPosition();
	}

	mt->graph = (double**)malloc(sizeof(double*) * (mt->n + 2));
	for (i = 0; i < 2; i++) {
		mt->graph[i] = (double*)malloc(sizeof(double)*(mt->n+2));

		for (j = 0; j < mt->n + 2; j++) {
			if (i == j) mt->graph[i][j] = 0;
			else {
				double dist = getDistance(mt->obj[i], mt->obj[j]);
				mt->graph[i][j] = dist / 5;
			}
			
		}
	}
	for (i = 2; i < mt->n+2; i++) {
		mt->graph[i] = (double*)malloc(sizeof(double) * (mt->n + 2));

		for (j = 0; j < mt->n + 2; j++) {
			if (i == j) mt->graph[i][j] = 0;
			else {
				double dist = getDistance(mt->obj[i], mt->obj[j]) - 50;
				if (dist < 0) dist *= -1;
				mt->graph[i][j] =  dist / 5 + 2;
			}
		}
	}

	doDijkstra(mt);

	// Free
	free(mt->obj);
	free(mt);

	return 0;
}

 

핵심은 루트가 매우 한정되어있으며 이것을 그래프화 시킬 수 있다는 것이다.

우선 인덱싱부터 하자면, 0은 시작 위치, 1은 도착 위치, 2~end는 대포들(입력받은 순서대로)이라고 하겠다.

먼저, 0에 있다고 하면 1~end에 5m/s로 이동하므로 가중치(소요 시간)은 dist/5이다. 다음으로 특정 대포에 있다고 했을 때는 가중치가 2 + |dist-50|/5이다. 우선 2초는 필수적으로 소요되며, 50을 이동하였으므로 거리에서 그만큼 뺀 뒤 나머지를 이동하는 것인데, 이 때 대포의 사정거리 안에 목적지가 위치할 경우를 대비하여 절댓값을 붙인 것이다.

이를 기반으로 그래프를 완성시켰으면 거의 끝났다고 보면 된다. 나머지는 다익스트라로 최단거리를 구해주기만 하면 된다.