[BOJ] 21738번 : 얼음깨기 펭귄 C++ 풀이

간단한 그래프 탐색 문제이다. 문제를 해석해보면, 직관적으로 펭귄과 가장 가까운 빨간 블록 2개를 찾고, 이 2개의 블록을 찾기까지 만나는 깰 수 있는 블록들의 개수를 세면 된다.

이게 가능한 이유는 그래프가 트리로 주어지고, 빨간 블록들이 서로를 찾으려면 무조건 펭귄을 지나야 하기 때문이다. 따라서 BFS나 DFS를 돌려 각 칸에 도달하기 까지 거리를 구하고, 1 <= S 사이에 있는 블록들 중 더 작은 값 2개를 찾자. 그리고 펭귄이 올라가있는 칸은 깰 수 없으므로 예외를 처리해주자.

 

#include <bits/stdc++.h>
#define MINF 0x7f7f7f7f
#define INF 20000000000
#define MOD 10007
#define NUM 200010
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
typedef pair<double, int> pdi;
int N, S, P;
int visited[2*NUM];
vector<int> adj[2*NUM];

void dfs(int curr) {
    for (int next : adj[curr]) {
        if (visited[next] != -1) continue;
        visited[next] = visited[curr] + 1;
        dfs(next);
    }
}

void init() {
    memset(visited, -1, sizeof(visited));
    cin >> N >> S >> P;
    for (int i=1; i<N; i++) {
        int x, y;
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    visited[P] = 0;
    dfs(P);
    priority_queue<int> pq;
    for (int i=1; i<=S; i++) {
        pq.push(-visited[i]);
    }
    int cnt = 0;
    cnt += (-pq.top());
    pq.pop();
    cnt += (-pq.top());
    cout << N - cnt -1 << '\n';
}       

int main(){
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    init();
}