[G5] 백준 9763번 마을의 친밀도 C++ 브루트포스 알고리즘

리뷰

 

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

한 마을에서 다른 두 마을까지의 거리의 합이 최소가 되는 거리를 구하는 문제

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• INF : 초기값을 정의할 상수 변수
• Pos : 좌표 정보를 정의할 구조체
• arr : 모든 마을의 좌표 정보를 저장할 Pos타입 배열
• n : 마을의 개수를 저장할 변수
• best1 : 각 마을에서 가장 가까운 마을의 거리를 저장할 배열
• best2 : 각 마을에서 두번째로 가까운 마을의 거리를 저장할 배열

 

함수

1. get_dist

int get_dist(const Pos& left, const Pos& right) {
	return abs(left.x - right.x) + abs(left.y - right.y) + abs(left.z - right.z);
}

 

각 마을간의 거리를 구하기 위한 함수

 

2. update

void update(int d, int& b1, int& b2) {
	if (d < b1) b2 = b1, b1 = d;
	else if (d < b2) b2 = d;
}

 

현재 마을과의 거리가 여태까지의 최소 거리와 업데이트를 진행할지 여부를 갱신하는 함수

 

 

문제풀이

1. n값을 입력 받고, n개 마을의 좌표를 입력 받아 arr배열을 초기화한다, best1, best2배열도 최대값으로 초기화해준다.
2. 브루트포스 알고리즘을 통해 각 마을에서 다른 마을까지의 최소 거리를 구해 best1, best2배열을 초기화한다.
3. 변수 ans를 INF로 초기화 하고, n개의 마을을 순회하며 두 마을까지의 거리합 중 가장 작은 값을 ans에 저장한다.
4. ans에 저장된 값을 출력한다.

 

트러블 슈팅

1. 처음엔 뇌를 빼고 모든 좌표간 거리를 구해준 뒤 정렬 후 0, 1번 인덱스의 합을 출력하였으나 메모리 초과를 받았다.
2. 모든 좌표간 거리 정보를 구하지 않고, 가장 가까운 거리 2개만 최신화 해주는 방식으로 로직을 수정해 AC를 받았다.

 

참고 사항

1. 단순 브루트포스를 사용한다고 해도 시간 복잡도는 O(N^2)으로 C++ 기준 1초 내에 통과할 수 있다고 판단했다.
2. 하지만 공간 복잡도가 O(N^2)이 된다면 메모리 초과로 인해 통과할 수 없었다.

 

정답 코드

#include<iostream>
using namespace std;

const int N = 1e4;
const int INF = 2e9;
struct Pos {
	int x, y, z;
};
Pos arr[N];
int n;
int best1[N], best2[N];

int get_dist(const Pos& left, const Pos& right) {
	return abs(left.x - right.x) + abs(left.y - right.y) + abs(left.z - right.z);
}

void update(int d, int& b1, int& b2) {
	if (d < b1) b2 = b1, b1 = d;
	else if (d < b2) b2 = d;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	for (int i = 0; i < n; ++i) {
		int x, y, z; cin >> x >> y >> z;
		arr[i] = { x, y, z };
		best1[i] = INF;
		best2[i] = INF;
	}

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < i; ++j) {
			int d = get_dist(arr[i], arr[j]);
			update(d, best1[i], best2[i]);
			update(d, best1[j], best2[j]);
		}
	}

	int ans = INF;
	for (int i = 0; i < n; ++i) {
		ans = min(ans, best1[i] + best2[i]);
	}
	
	cout << ans;
}