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

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

21278번: 호석이 두 마리 치킨

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 그래프 이론
• 브루트포스 알고리즘
• 플로이드-와샬

 

---

 

⊙ 문제 접근 과정

 

플로이드 와샬을 통해 문제를 풀었다.

먼저 길 없음을 표시하고 입력을 통해 주어진 M개의 길을 뚫어준다.

 

그다음 플로이드 와샬 알고리즘을 통해 거쳐가는 값이 존재하면 갱신!

그리고 2중 for문을 통해 브루트포스를 구현했다.

 

배열 v를 만들고 브루트포스를 통해 탐색한 거리를 전부 저장했다.

그리고 저장한 배열 값들을 총 거리순으로 오름차순 정렬했다.

 

정렬의 경우 직접 구현했는데 거리순으로 먼저 오름차순 정렬한다.

만약 같은 값이 존재한다면 첫 번째 건물 번호가 작은 순으로 오름차순 정렬!

거리도 같고 첫 번째 건물 번호도 같다면, 두 번째 건물 번호도 참조하여 오름차순을 진행했다.

 

마지막으로 배열에서 제일 앞에 있는 값을 출력해줬다. (오름차순)

 

아래 코드를 통해 확인해보자!

---

 

⊙ 문제 풀이

 

#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>

using namespace std;
#define MAX 101

const int INF = 999999;
int N, M;
int arr[MAX][MAX];
vector<tuple<int,int,int>> v;

//왕복 시간 정렬 후, 건물 번호 작은 것 정렬 (직접 구현)
bool compare(const tuple<int, int, int>& a, const tuple<int, int, int>& b) {
    if(get<2>(a) == get<2>(b)) {
        if(get<0>(a) == get<0>(b))
            return get<1>(a) < get<1>(b);
        return get<0>(a) < get<0>(b);
    }
    return get<2>(a) < get<2>(b);
}

int main() {
    cin >> N >> M;

    //길 없음을 표시
    for(int i=1;i<=N;i++) {
        for(int j=1;j<=N;j++) {
            arr[i][j]=INF;
            if(i==j) arr[i][i]=0;
        }
    }

    //길 있음을 표시
    for(int i=0; i<M;i++) {
        int x,y;
        cin >> x >> y;
        arr[x][y]=arr[y][x]=1;
    }

    //플로이드 와샬
    for(int k=1;k<=N;k++)  //k = 거쳐가는 노드
        for(int i=1;i<=N;i++)  // i = 출발 노드
            for(int j=1; j<=N;j++)  // j = 도착 노드
                if(arr[i][j] > arr[i][k] + arr[k][j]) //더 작은 값
                    arr[i][j] = arr[i][k] + arr[k][j];

    for(int i=1;i<N;i++) {
        for(int j=i+1;j<=N;j++) {
            int distance=0;
            for(int k=1;k<=N;k++) {
                distance += min(arr[k][i], arr[k][j])*2; //거리
            }
            //(건물번호, 건물번호, 총 거리) 배열에 저장
            v.push_back({i,j,distance});
        }
    }

    //크기 정렬!! (compare 직접 구현)
    sort(v.begin(),v.end(),compare);
    //가장 작은 값 출력
    cout << get<0>(v[0]) << " " << get<1>(v[0]) << " " << get<2>(v[0]);
}

---

⊙ 결과

 

---

⊙ 마무리

 

 

NONE

 

좋아요는 로그인하지 않아도 누를 수 있습니다!