(Python) - BOJ(21738번) : 얼음깨기 펭귄

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

21738번: 얼음깨기 펭귄

---

• 문제 : 

도도는 심심해서 보드게임 카페에 갔다. 마침 평소에 즐겨 했던 얼음 깨기 펭귄의 업그레이드 버전으로 특수 얼음 깨기 펭귄 보드게임이 나와 직접 플레이해 보기로 결정했다. 특수 얼음 깨기 펭귄 게임은 특수 안경이 있어 특수 안경을 끼고 얼음들을 보면 얼음들 간의 연결 관계가 보인다.

특수 얼음 깨기 펭귄 게임에 있는 얼음의 종류로는 지지대의 역할을 하는 얼음과 일반 얼음 총 2가지의 얼음이 존재한다. 지지대의 역할을 하는 얼음의 경우, 빨간색으로 구분하여 볼 수 있으며 일반 얼음을 지탱해 주어 일반 얼음들이 깨지지 않도록 도와준다. 일반 얼음의 경우에는 1개의 지지대만이 연결되어 있어도 얼음이 깨지지 않지만 펭귄이 올라가 있는 얼음은 2개 이상의 지지대의 역할을 하는 얼음이 연결되어 있어야만 얼음이 깨지지 않는다. 이때, 지지대가 연결되어 있다는 것은 지지대로부터 서로 다른 일반 얼음들을 통해 연결 관계가 이어져 있는 것을 이야기한다. 특수 얼음 깨기 펭귄 게임에서 도도가 펭귄을 떨어뜨리지 않고 최대 몇 개의 얼음을 깰 수 있을까?

 

 

 

---

• 풀이 :

탐색 문제다. 펭귄이 위치한 현재 블록에서 bfs로 탐색하며 각 블록과 연결되어있는 얼음들을 탐색한다. 이 때, 지지대 역할을 하는 얼음의 번호가 1부터 S까지이므로 깨려는 얼음이 S번 이하의 번호라면 카운트를 증가시킨다.

카운트를 증가시키는 이유는 가장 짧은 거리에 있는 지지대 얼음의 개수를 세기 위함이다.

찾은 지지대 얼음이 총 2개(cnt == 2)가 되었을 때, 이 두 지지대 얼음만 남기고 나머지 모든 얼음을 깰 수 있다는 것이므로 (지지대 두 개만 있으면 나머지는 전부 깨도 상관없다.) 아직 깨지지 않은 얼음과 이미 깬 얼음의 수를 전부 더하면 된다.

 

 

 

 

---

• 소스코드 : 

 

import sys
from collections import deque
input = sys.stdin.readline
 
if __name__ == "__main__":
    N,S,P = map(int,input().split())
    c = [0 for _ in range(N+1)]
    for i in range(S):
        c[i] = 1
    link = [[] for _ in range(N+1)]
    for _ in range(N-1):
        a,b = map(int,input().split())
        link[a].append(b)
        link[b].append(a)
 
    queue = deque()
    queue.append(P)
    cnt = 0
    c[P] = 1
    ans = []
    while queue:
        idx = queue.popleft()
        for i in link[idx]:
            if i <= S:
                cnt += 1
                ans.append(c[idx])
                if cnt == 2:
                    print(N-1-sum(ans))
                    exit()
            if c[i] == 0:
                c[i] = c[idx] + 1
                queue.append(i)