1247. [S/W 문제해결 응용] 3일차 - 최적 경로

 

처음에 다익스트라인가 했다가 크루스칼인가 했다가 문제 자세히 보니 효율적인 경로 찾기 문제가 아니였다.

즉 시간복잡도 측에서 줄여야 하는 문제가 아닌것을 확인.

시간을 C++ 기준 10초나 줬다.

그래서 DFS로 풀어버림.

다익스트라는 어떤 출발점에서 도착점

처음에 다익스트라인가 했다가 크루스칼인가 했다가 문제 자세히 보니 효율적인 경로 찾기 문제가 아니였다.

 

즉 시간복잡도 측에서 줄여야 하는 문제가 아닌것을 확인.

 

시간을 C++ 기준 10초나 줬다.

 

그래서 DFS로 풀어버림.

 

다익스트라는 어떤 출발점에서 도착점까지 최단거리로 이동하는 것이고

크루스칼은 간선마다 가중치가 존재하는데 도착점이 정해지지 않고 최소비용으로만 연결된 트리를 만들어 내는 것이 목적.

즉 어떤 지점에서 어떤 지점으로의 이동이 목적이 아니라 여러 간선들이 있으면 최소 비용으로 정점들을 연결하는 것이 목적.

 

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

using namespace std;

struct Node{
	
	int x;
	int y;
	int idx;
};



Node customer[10];
bool visit[10];

int N;
int startx,starty,endx,endy;
int result ;
int current ;

void DFS(int x, int y, int count)
{
	

	if(count == N )
	{
		
		current += abs(endx-x) + abs(endy -y);
		
		if(result > current)
		{
			
			result = current;
			
		}
		
		current -= abs(endx-x) + abs(endy -y);
	}
	else
	{
		
	

	
	for(int i = 0; i < N; i++)
	{
		
		if(!visit[i])
		{
			visit[i] = true;
			current += abs(customer[i].x-x)+abs(customer[i].y-y);
			
			DFS(customer[i].x,customer[i].y,count+1);
			current -= abs(customer[i].x-x)+abs(customer[i].y-y);
			visit[i] = false;
		}
	}
	
	}
	
	
}

int main(void)
{
	
	
	
	
	int test_case;
	cin >> test_case;
	
	for(int tc =1 ; tc <= test_case; tc++)
	{
		
		
		cin >> N;
		
		result = 987654321;
		current = 0;
		
		cin >> startx >> starty;
		cin >> endx >> endy;
		
		
		
		
		for(int i = 0; i < N; i++ )
		{
			
			cin >> customer[i].x >> customer[i].y;
			customer[i].idx = i;
			visit[i] = false;

		}	
		
		DFS(startx,starty, 0);
		
		
		cout << "#"<<tc<<" "<<result<<endl;
		
	}
	
	return 0;
}