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

문제 바로가기 : https://www.acmicpc.net/problem/21738

메모리 : 143924KB

시간 : 648ms

언어 : Java 11

---

코드

 import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static class Node {
        int num, depth;

        Node(int num, int depth) {
            this.num = num;
            this.depth = depth;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()); // 전체개수
        int S = Integer.parseInt(st.nextToken()); // 지지대
        int P = Integer.parseInt(st.nextToken()); // 펭귄
        List<List<Integer>> list = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            list.add(new ArrayList<>());
        }
        for (int i = 1; i < N; 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);
        }
        boolean[] check = new boolean[N + 1];
        Queue<Node> q = new LinkedList<>();
        int cnt = 0;
        int save = 1; //펭귄자리 하나
        check[P] = true;
        q.add(new Node(P, 0));
        loop: while (!q.isEmpty()) {
            Node n = q.poll();
            for (int k = 0; k < list.get(n.num).size(); k++) {
                // 지지대에 도착했다면
                if (list.get(n.num).get(k) <= S) {
                    cnt++;
                    save += n.depth + 1;
                    if (cnt == 2)
                        break loop;
                    continue;
                }
                if (!check[list.get(n.num).get(k)]) {
                    check[list.get(n.num).get(k)] = true;
                    q.add(new Node(list.get(n.num).get(k), n.depth + 1));
                }
            }
        }
        System.out.println(N - save);
    }
}

풀이

펭귄이 서있는 지점에서 가장 가까운 지지대 두 개를 선택해야한다. 지지대는 1~S번이기 때문에 bfs탐색을 하면서 S번 이하의 얼음을 만났을 때 그 깊이를 저장하면 된다.

1. 서로 다른 두 얼음을 잇는 경로는 하나뿐이다. -> 트리라는 뜻이다. 루트는 펭귄이 서 있는 곳이 되겠다.
2. 펭귄을 시작으로 너비우선 탐색을 한다. 깊이 우선 탐색을 하는 경우 모든 맵을 다 돌고 지지대까지의 최소거리 2개를 골라야하기 때문에 시간초과가 날 것이다. 너비 우선 탐색으로 낮은 레벨부터 순회하며 지지대 2개를 만난 순간 종료해준다.
3. 전체 얼음의 개수에서 꼭 있어야 하는 지지대 두개를 연결한 선을 뺀 나머지는 다 뿌셔도 된다.

1등!