(C++) - 백준(BOJ) 21738번 : 얼음깨기 펭귄

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

21738번: 얼음깨기 펭귄

dijkstra로 해결한 문제였습니다.

 

 

풀이방법

 1. 간선을 인접리스트 형태로 저장합니다.

 

 2. 펭귄 위치에서 i번째 얼음 볼록으로 가는 최단거리를 모두 저장합니다. 거리가 모두 1이기 때문에 이것이 곧 깰 수 있는 얼음의 개수가 됩니다. 즉, i번 얼음 블록을 깬다면 연쇄적으로 펭귄과의 최단거리만큼의 얼음이 깨진다는 의미입니다.

 

 3. 1 ~ s 까지는 지지대 얼음이기 때문에 최대한으로 깨려면 가장 가까운 지지대 얼음 블록 2개를 제외하면됩니다. 따라서 구한 최단 거리들을 배열에 저장한뒤에 0 ~ s + 1까지 오름차순으로 정렬하고 n에서 0번째와 1번째를 제외한 값을 반환 후 출력해줍니다.

 

Code

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
using pii = pair<int,int>;
vector <int> block[328001];
int dist[328001];
int n, s, p;

int dijkstra(){
    priority_queue <pii,vector<pii>,greater<pii>> minHeap;
    dist[p] = 0;
    minHeap.push({0,p});
    while(!minHeap.empty()){
        int cost = minHeap.top().first;
        int cur = minHeap.top().second;
        minHeap.pop();
        if(dist[cur] < cost) continue;
        for(auto next : block[cur]){
            if(dist[next] > dist[cur] + 1 ){
                dist[next] = dist[cur] + 1;
                minHeap.push({dist[next],next});
            }
        }
    }
    sort(dist,dist + s + 1);
    return n - dist[0] - dist[1] - 1;
}

int main(){
    cin >> n >> s >> p;
    memset(dist,INF,sizeof(dist));
    for(int i = 0,a,b; i < n - 1; i++){
        cin >> a >> b;
        block[a].push_back(b);
        block[b].push_back(a);
    }
    cout << dijkstra();

}