백준 21738번 얼음깨기 펭귄 [C++]

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

 

 

#문제 간단 정리

 

bfs 문제

 

#문제 해결 방법

 

우선 문제를 잘 이해해 보면

펭귄이 이어진 지지대가 2개 는 있어야 된다 

-> 즉 펭귄과 지지대를 잇는 경로만 멀쩡히 있으면 된다

-> 즉 가장 가까운 지지대 2개를 골라서 그 지지대 경로를 제외한 모든 얼음을 깨면 된다

-> 가장 가까운 지지대 2개를 bfs 를 이용해서 찾는다

 

라는 발상이 가능하다

중요한건 dfs 를 처음에 사용하려 했는데 가장 가까운 지지대 경로 를 찾아야해서 

부적합 하기 때문에 bfs 를 사용했고 ,( 재귀형식으로 만드는ㄴ게 불가능하진 않겠지만 귀찮을 것이다)

 

그리고 결국 가장 가까운 거리의 2개의 지지대 경로만 찾으면 되기 때문에

2개를 찾자마자 바로 결과를 출력했다.

딱히 거리만 같으면 되니까 더 탐색할 이유가 없다.

 

 

 

 

#전체 코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, s, p;
    cin >> n >> s >> p;

    // 인접 리스트 준비
    vector<vector<int>> graph(n + 1);
    vector<bool> visited(n + 1, false);

    // 간선 입력 (트리 구조)
    for (int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    // BFS 준비
    queue<pair<int, int>> q;
    q.push({ p, 0 });
    visited[p] = true;

    bool find = false;
    int ans = 0;

    while (!q.empty()) {
        // queue에서 (현재 노드, 거리) 꺼내기
        int now = q.front().first;
        int dist = q.front().second;
        q.pop();

        // 현재 노드에 인접한 노드 탐색
        for (auto next : graph[now]) {
            // 아직 방문하지 않은 경우만
            if (!visited[next]) {
                visited[next] = true;

                // 지지대 노드(번호 <= s) 발견 시 처리
                if (next <= s) {
                    // ans가 0이면 첫 번째 지지대,
                    // 그 뒤면 두 번째 지지대라는 가정으로 ans 계산
                    if (find == false) {
                        ans -= (dist + 1);
                        find = true;
                    }
                    else {
                        ans -= (dist + 1);
                        cout << n + ans - 1 << endl;
                        return 0;
                    }
                }
                else {
                    // 일반 노드는 계속 큐에 넣어서 탐색
                    q.push({ next, dist + 1 });
                }
            }
        }
    }




    return 0;
}