1247.최적경로

1247. 최적경로

문제에서 나와있듯이 그냥 모든 경로를 탐색하면서 최소값을 찾아주어도 시간제한이나 메모리제한에 걸리지 않는다. 그래서 그냥 부르트포

스를 이용해서 문제를 해결했다.

한 집의 위치정보와 그 집을 방문했는지 여부를 구조체를 이용해서 만들어주었다.

house 변수의 0번째를 출발하는 집으로, 1번째를 도착하는 집으로 설정하였고, 재귀함수를 이용해서 모든 경우를 탐색하였다.

재귀함수의 매개변수로 이전의 값들을 저장하면서 거리를 구하면서 재귀함수를 실행시켰다.

그리고 마지막으로 도착점과 그 이전 점과의 거리를 더해주고 정답과 비교하면서 최소값을 찾아냈다.

<정답 코드>

#include<iostream>
#include<vector>
 
#define INF 987654321;
 
using namespace std;
 
int ans;
typedef struct pos {
    int x;
    int y;
    bool visited;
}pos;
 
void dfs(vector<pos> &house, int k, int N,int len,int before)
{
    if (k == N)
    {
        len += ((abs(house[1].x - house[before].x) + abs(house[1].y - house[before].y)));
 
        if (ans > len)
            ans = len;
 
        return;
    }
 
 
    for (int i = 2; i < house.size(); i++)
    {
        if (!house[i].visited)
        {
            house[i].visited = true;
            dfs(house, k + 1, N, len + abs(house[i].x - house[before].x) + abs(house[i].y - house[before].y), i);
            house[i].visited = false;
        }
    }
 
}
 
int main()
{
    int tc;
    cin >> tc;
 
    for (int t = 1; t <= tc; t++)
    {
        int N;
        ans = INF;
        cin >> N;
        vector<pos> house(N + 2);
 
        for (int i = 0; i < N + 2; i++)
        {
            cin >> house[i].x >> house[i].y;
            house[i].visited = false;
        }
 
        dfs(house,0,N,0,0);
 
        cout << "#" << t << " " << ans << endl;
    }
 
    return 0;
}