글 읽기 - 문제 로직좀 봐주실 수 있나요?

yeongjae8066 4년 전 0

최단경로로 풀어야한다는 점은 도움을 얻어서 알게 됐습니다.

답은 맞았는데, N이 작다보니 N이 클때 로직이 맞는지좀 알려주세요

먼저 각 정점간에 거리를 구한다
플로이드로 갱신한다
0을 시작으로 뒷 부분을 순열을 돌려서 완전탐색을 했습니다

이 로직이 맞는지 궁금합니다

#include <cmath>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

struct point {
	int x, y;
	point() {}
	point(int x, int y) : x(x), y(y) {}
};

point a[4];
double d[4][4];
vector<int> pm;

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	for (int i = 0; i < 4; i++) {
		cin >> a[i].x >> a[i].y;
	}
	for (int i = 0; i < 4; i++) {
		int x1, y1;
		x1 = a[i].x, y1 = a[i].y;
		for (int j = 0; j < 4; j++) {
			if (i == j) continue;
			int x2, y2;
			x2 = a[j].x, y2 = a[j].y;
			double dist;
			dist = sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
			d[i][j] = d[j][i] = dist;
		}
	}

	for (int k = 0; k < 4; k++) {
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				if (d[i][j] > d[i][k] + d[k][j]) {
					d[i][j] = d[i][k] + d[k][j];
				}
			}
		}
	}

	double ans = -1;
	pm = { 0, 1, 2, 3 };
	do {
		double sum = 0;
		int st = pm[0];
		for (int i = 1; i < 4; i++) {
			sum += d[st][pm[i]];
			st = pm[i];
		}
		if (ans == -1 || ans > sum) {
			ans = sum;
		}
	} while (next_permutation(pm.begin() + 1, pm.end()));

	cout << (int)ans << '\n';
	return 0;
}

sanha93 4년 전 0

어차피 완전 탐색을 하려는데, 굳이 앞에서 플루이드를 할 필요가 있을까요?

그냥 바로 완전 탐색을 돌리면 되는 문제같아요.

https://mountrivers.github.io/boj17286/

여기 함 참고 해 보세요.

만약 최단거리를 이용하여 구하고 싶으시면

그냥 최단거리를 구하는게 아닌 모든 경로를 거친 후 B,C,D 에 도착하는 최단 거리를 구해야 함으로

사실상 완전탐색이나 마찬가지가 돼서요.

플로이드는 중간에 어딜 거치는지 보단, 목적지까지 얼마만에 갈수 있냐 때문에..

yeongjae8066 4년 전 0

맞네요. 감사합니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

문제 로직좀 봐주실 수 있나요?

yeongjae8066 4년 전 0

sanha93 4년 전 0

yeongjae8066 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말