Lee's Programming Practice

문제

* 해당 문제의 모든 저작권은 SWEA 측에 있으며 본 블로그는 SWEA  약관을 위배하지 않음을 명시합니다.*

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15OZ4qAPICFAYD 

풀이

순열 || DFS

본인은 DFS를 선택해서 풀이함.

1. DFS를 활용해 탐색함.

2. 백트래킹 기법을 이용해서 기존의 최소거리보다 탐색중 거리가 길어지면 돌리지 않음

소스 코드

// Library
#include <iostream>
#include <string>
#include <stack>
#include <set>
#include <queue>
#include <deque>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <map>
#include <cctype>
#include <set>
#include <string.h>
#include <string>
 
// std::
using namespace std;
 
// Sturct
struct point {
    int x;
    int y;
};
 
// Test_case
int T, test_case;
 
// Value
int N;
point arr[10];
point home;
point comp;
bool visit[10] = { false };
int minl = 987654;
 
// Matrix direction
//int dx[4] = { 0, 0, 1, -1 };
//int dy[4] = { 1, -1, 0, 0 };
 
// Dist
int dist(point a, point b) {
    return abs(a.x - b.x) + abs(a.y - b.y);
}
 
void DFS(int d, point p, int len)
{
    if (d == N) {
        minl = min(minl, len + dist(p, comp));
        return;
    }
    else if (len > minl) {
        return;
    }
 
    for (int i = 0; i < N; i++)  {
        if (!visit[i]) {
            visit[i] = true;
            DFS(d + 1, arr[i], len + dist(p, arr[i]));
            visit[i] = false;
        }
    }
    return;
}
 
// Main function
int main() {
    // cin, cout
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
     
    // SWEA 양식
    // T = 10;
    cin >> T;
    for (test_case = 1; test_case <= T; test_case++) {
         
        cin >> N;
 
        minl = 987654;
        memset(visit, false, sizeof(visit));
 
        cin >> comp.x >> comp.y;
        cin >> home.x >> home.y;
 
        for (int i = 0; i < N; i++) {
            cin >> arr[i].x >> arr[i].y;
        }
         
        DFS(0, home, 0);
 
        cout << "#" << test_case << " " << minl << '\n';
    }
         
    return 0;
}