[백준] 21278번 호석이 두 마리 치킨 (C++)

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

 

 

이 문제는 N개의 노드가 있을때 N개중 2개의 노드를 치킨집으로 지정하고 N-2개의 노드에 대해서 가장 가까운 치킨집의 거리의 합을 최소로 만드는 노드를 출력하는 문제이다.

 

1. N개의 노드 중 각각의 노드에 대해서 거리를 기록해야한다.

 

2. N개중 2개를 선택하는 경우의 수를 구해야한다.

 

저 2개의 문제만 해결하면 간단하게 풀 수 있다. 

1번을 해결하기 위해서 플로이드 워셜을 사용하여 모든 노드에 대한 거리를 알아내었으며

2번은 백트래킹 조합을 사용하여 가지 수를 알아내었으며 최소거리를 알아내기 위해서 2번 모든 조합을 탐색하며 최솟값과 노드를 기록하고

 

최솟값이 업데이트될 경우 노드를 업데이트 하였다.

 

 

정답코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    int y;
    int r;
};

int dx[] = {-1, 1, 0, 0, 1, -1, -1, 1};
int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
int N, M;
int graph[101][101];
bool visited[101];
int answer = MAX;
pii ans = {MAX, MAX};
int arr[2];

void Init() {
    for(int i = 1; i <= N; i++) {
        for(int j = 1; j <= N; j++) {
            if(i == j) continue;
            graph[i][j] = MAX;
        }
    }
}

void Print() {
    for(int i = 1; i <= N; i++) {
        for(int j = 1; j <= N; j++) {
            cout << graph[i][j] << " ";
        }
        cout << endl;
    }
}

void bt(int x, int cnt) {
    if(cnt == 2) {
        int tmpdist = 0;

        for(int i = 1; i <= N; i++) {
            bool flag = false;
            int dist = MAX;
            for(int j = 0; j < 2; j++) {
                if(arr[j] == i) {
                    flag = true;
                    break;
                }
            }
            if(!flag) {
                dist = min(graph[arr[0]][i], graph[arr[1]][i]);
                tmpdist += dist;
            }
        }

        tmpdist *= 2;

        if(answer > tmpdist) {
            answer = tmpdist;
            ans.first = arr[0];
            ans.second = arr[1];
        }
        else if(answer == tmpdist) {
            if(ans.first > arr[0]) {
                ans.first = arr[0];
                ans.second = arr[1];
            }
            else if(ans.first == arr[0]) {
                if(ans.second > arr[1]) {
                    ans.first = arr[0];
                    ans.second = arr[1];
                }
            }
        }
        return;
    }

    for(int i = x; i <= N; i++) {
        if(!visited[i]) {
            visited[i] = true;
            arr[cnt] = i;
            bt(x+1, cnt+1);
            visited[i] = false;
        }
    }
}

void solve() {
    for(int k = 1; k <= N; k++) {
        for(int i = 1; i <= N; i++) {
            for(int j = 1; j <= N; j++) {
                graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);
            }
        }
    }

    bt(1, 0);

    cout << ans.first << " " << ans.second << " " << answer;
}

void input() {
    cin >> N >> M;

    Init();

    for(int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        graph[a][b] = 1;
        graph[b][a] = 1;
    }
}


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

    input();
    solve();
}