ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 백준 14619번 c++ 풀이
    백준 2019. 11. 24. 12:04
    
    #include <iostream>
    #include <climits>
    #include <cstring>
    #include <queue>
    #include <algorithm>
    #include <map>
    #include <list>
    #include <stack>
    
    
    using namespace std;
    
    class IslandManager {
    
    public:
        IslandManager(int n) {
            this->n = n;
            this->bridgeBuffer = new bool*[n];
            this->heightBuffer = new int[n];
    
            for (auto i=0; i<n; i++) {
                this->bridgeBuffer[i] = new bool[n] {false} ;
            }
        }
    
        void setHeight(int index, int height) {
            this->heightBuffer[index]=height;
        }
        void setBridge(int to, int from) {
            to--;
            from--;
            this->bridgeBuffer[to][from]=true;
            this->bridgeBuffer[from][to]=true;
        }
    
        int findLowerIsLand(int from, int bridgeNumber) {
            from--;
            bool * isVisited = new bool[n] {false};
            isVisited[from] = true;
            for (auto i=0; i<bridgeNumber; i++) {
    
                bool *nextVisited = new bool[n] { false };
    
                for (auto j = 0; j<n; j++) {
                    if (isVisited[j]) {
                        for (auto k=0; k<n; k++) {
                            if (this->bridgeBuffer[j][k]) {
                                nextVisited[k] = true;
                            }
                        }
                    }
                }
    
                bool sameAsBefore = true;
                for (auto j=0; j<n; j++) {
                    if (isVisited[j] != nextVisited[j]) {
                        sameAsBefore = false;
                    }
                    isVisited[j] = nextVisited[j];
                }
                if (sameAsBefore) {
                    break;
                }
            }
            int minimumHeight = INT_MAX;
    
            for (auto index = 0; index<n; index++) {
                if (isVisited[index]) {
                    minimumHeight = min(minimumHeight, this->heightBuffer[index]);
                }
            }
            if (minimumHeight == INT_MAX) {
                return -1;
            } else {
                return minimumHeight;
            }
        }
    
    private:
        bool ** bridgeBuffer;
        int * heightBuffer;
        int n;
    
    };
    
    int main() {
        ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
        int n, m;
        cin >> n >> m;
        IslandManager *manager = new IslandManager(n);
        for (auto i=0; i<n; i++) {
            int height;
            cin >> height;
            manager->setHeight(i, height);
        }
    
        for (auto i=0; i<m; i++) {
            int from, to;
            cin >> from >> to;
            manager->setBridge(to, from);
        }
    
        int t;
        cin >> t;
        for (auto i=0; i<t; i++) {
            int a, k;
            cin >> a >> k;
            cout << manager->findLowerIsLand(a, k) << '\n';
        }
        return 0;
    }

    '백준' 카테고리의 다른 글

    백준 16681번 풀이  (0) 2019.12.01
    PS(알고리즘) 오픈 톡방 신입부원 대 모집!!  (0) 2019.12.01
    백준 14612번 C++ 풀이  (0) 2019.11.21
    백준 13413번 C++ 풀이  (0) 2019.11.09
    백준 2096번 C++ 풀이  (0) 2019.10.29

    댓글 0

Designed by Tistory.