[백준] 21738: 얼음깨기 펭귄 - JAVA

in Algorithm on 그래프 이론

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

풀이

그래프 탐색 문제.

펭귄이 얼음 위에 올라가있는데 떨어지지 않으려면 연결된 지지대 얼음 2개가 필요하다.

최소한의 얼음만 남기고 얼음을 깨야한다.

펭귄의 위치로부터 탐색한다.

먼저 발견한 얼음이 가깝다는 것이므로

먼저 발견한 2개의 지지대 얼음을 제외한 나머지 얼음은 깨는 것으로 한다.

메모리: 152136KB

시간: 696ms

언어: Java 11

코드

import java.io.*;
import java.util.*;

public class Main {
    static int N, S, P, ans;
    static ArrayList<ArrayList<Integer>> list;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken()); // 얼음 블록의 개수
        S = Integer.parseInt(st.nextToken()); // 지지대 얼음의 개수
        P = Integer.parseInt(st.nextToken()); // 펭귄의 위치

        list = new ArrayList<>();
        for (int i = 1; i <= N + 1; i++) {
            list.add(new ArrayList<>());
        }

        for (int i = 0; i < N - 1; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            list.get(a).add(b);
            list.get(b).add(a);
        }

        ans = N - 1;

        bfs(P);

        System.out.println(ans);
    }

    private static void bfs(int start) {
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visit = new boolean[N + 1];
        queue.add(start);
        visit[start] = true;

        int depth = -1; // 펭귄으로부터 거리
        int closeCnt = 0; // 탐색된 지지대의 개수
        // 지지대 2개가 필요하므로 가장 가까운 지지대 2개만 살리고 나머지를 깬다
        while (!queue.isEmpty() && closeCnt < 2) {
            depth++;
            int len = queue.size();
            for (int i = 0; i < len; i++) {
                int num = queue.poll();
                if (num <= S && closeCnt < 2) {
                    ans -= depth;
                    closeCnt++;
                    continue;
                }

                for (int next : list.get(num)) {
                    if (!visit[next]) {
                        queue.add(next);
                        visit[next] = true;
                    }
                }
            }
        }
    }

}