백준알고리즘 2585번

그래프탐색과 이분탐색을 활용해서 푸는 문제이다.

이번 문제에서 중점은 어떤 값을 기준으로 이분 탐색을 돌릴 것인지 찾는 것이였는데 한참을 고민하다가 연료통을 기준으로 돌려야 겠다고 생각했다.

이분탐색의 경우 한동안 알고리즘 스터디를 진행하면서 문제를 자주 풀었기 때문에 어느정도 손쉽게 구현할 수 있었다.

이분탐색의 기본적인 형태는 아래와 같다.

void binary_search()
{
	int start;
	int mid;
	int end;
	
	while (start <= end)
	{
		mid = (start + end) / 2;
		if(내가 찾고자 하는값과 mid값 비교)
			end = mid - 1;
		else
			start = mid + 1;
	}
}

그래프 탐색의 경우 깊이우선탐색(dfs)와 너비우선탐색(bfs)로 크게 나누어져 있는데 bfs의 경우 아직은 익숙하지 않아서 dfs를 활용해 문제를 풀게 되었다.

dfs의 기본적인 형태는 다음과 같다.

bool dfs(params)
{
	if (탈출조건)
		return false;
	//방문노드 처리
	visited = true; 
	//루프를 활용한 노드 탐색
	for (루프)
	{
		if (추가조건)
		if (dfs성립조건)
			return true;
	}
}

그래프 탐색의 경우 제시되는 모든 좌표들을 미리 생성할 필요 없이 문제에서 주어지는 노드들만 활용해서 해결할 수 있다. 예를들어 1000 x 1000 좌표에서 특정 점들을 방문한다고 했을 때, 1000 x 1000 2차원배열을 유지할 필요 없이 n개의 배열과 n개의 방문배열만으로도 구현을 할 수 있다는 것이다. 따라서 탐색에 필요한 시간이 현저히 줄어들게 된다.

이번 문제에서는 start값과 end값을 찾는 것이 가장 어려웠는데 피타고라스 정리를 활용해서 최대값을 찾을 수 있었다.

최소값은 연료통의 크기가 1일때이다.

최대값은 10000 x 10000에서 특정 두 점을 잡았을때 나올 수 있는 가장 큰 길이이다. 따라서 피타고라스정리를 활용해

14142.1....

라는 값이 나온다.

처음에는 경유지의 개수에 따라 최대값의 크기와 최소값의 크기가 달라져야 한다고 생각했으나 애초에 이분탐색의 경우 그정도 크기는 depth가 몇번 차이가 나지 않고 범위를 좁힐수록 원하는 값이 최소값에 가까워지기 때문에 오히려 탐색 시간이 오래 걸릴 수 있다는 사실을 알아내었다.

C++언어를 활용하여 해결하였으며

vector, pair 자료구조를 활용해 점들의 좌표를 저장하였고

bool타입 vector를 활용해 방문좌표들을 체크하였다.

visited같은 경우 memset을 사용하지 않고 생성자를 사용하여서 초기화를 진행하였다.

함수내부의 콜스텍 부담을 줄이고 가시적인 코드를 위해 목적에 맞게 코드를 모듈화 하였다.

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

std::vector<std::pair<int, int> > station;
std::vector<bool> visited;

int n;
int k;
int result;

void input()
{
	std::cin >> n >> k;
	station.resize(n + 1);
	station[0] = std::make_pair(0, 0);
	for (int i = 1 ; i <= n; i++)
		std::cin >> station[i].first >> station[i].second;
}

int cal(int x1, int y1, int x2, int y2)
{
	return ((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
}

bool dfs(int idx, int mid, int count)
{
	if (count > k)
		return false;
	visited[idx] = 1;
	for (int i = 1 ; i <= n ; i++)
	{
		if (visited[i] || cal(station[idx].first, station[idx].second, station[i].first, station[i].second) > mid)
			continue ;
		if (cal(station[i].first, station[i].second, 10000, 10000) <= mid || dfs(i, mid, count + 1))
			return true;
	}
	return false;
}

void solution()
{
	int left = 1;
	int mid;
	int right = 14143;

	while (left <= right)
	{
		mid = (left + right) / 2;
		visited = std::vector<bool>(n, false);
		if (dfs(0, mid * mid * 100, 0))
			right = mid - 1;
		else
			left = mid + 1;
	}
	result = left;
}

void preset(){
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);
}

void output(){std::cout << result; }

int main(){
	preset();
	input();
	solution();
	output();
}